CODEWITHSUNDEEP
algorithmkeyheap
user2889303
user2889303

Reputation: 1

Two Heaps with same key Algorithms

Hi if you have two heaps how do you determine if they have a key that is the same in O(nlogn) runtime, where n is the total size between the two min heaps.

I was thinking that it might be related to adding one of the heaps to the other but I am not positive.

Upvotes: 0

Views: 455

Answers (2)

notbad
notbad

Reputation: 2887

bool have_same_element(heap<int> h1, heap<int> h2) {
  while (!h1.empty() && !h2.empty()) {
    int t1 = h1.top(), t2 = h2.top();
    if (t1 == t2) return true;
    if (t1 < t2) h1.pop();
    else h2.pop();    
  }
  return false;
}

O(s1 ln(s1) + s2 ln(s2)) guarantee O(n ln(n)) where n = s1+s2;

Upvotes: 1

Andrei Galatyn
Andrei Galatyn

Reputation: 3432

I think heap structure doesn't help to solve such task, so it doesn't matter if you have two heaps or two arrays of items. To find if two dataset have same value you can use different algorythms, i suggest two for example:

  1. You can put items of smaller set into any hash-based dictionary and then you can enumerate items of another set and check whether they are in first set. Probably it is fastest way, but takes some additional space for dictionary.

  2. Let's suppose you have 2 classical heap structures kept in arrays (for heap it is possible). Then you can sort smallest array. After that just enumerate items of the second heap and use binary search to check if item is in first heap. When you finish, you can rebuild your broken heap again (it is possible to do inline into same array wheere items are). So you get O(nlogn) where n is number of smaller heap and can do without additional memory usage.

Upvotes: 0

Related Questions