So I been practicing a couple of interview questions from my data structures book and one question that I'm not particularly sure of goes like this.
"Let H1 and H2 be two (binary) max-heaps with n1 and n2 elements respectively. If every element in H1 is larger than every element in H2, design an algorithm that merges these two heaps into one (binary) max-heap in O(n2) time (assume that both H1 and H2 are large enough to hold n1 + n2 elements)."
Normally I would say use a binomial heap for efficient merging of two heaps but the question says that it wants to merge two binary max heaps into one binary max heap. The trick is I'm assuming is that I need to take advantage of the fact that all of the elements in H1 are bigger than H2. So would it be correct to say that all I would have to do is insert all elements from H2 into H1(assume that both H1 and H2 are large enough to hold n1 + n2 elements) since every element in H1 is larger than every element in H2. The reason for this is because if all elements in H1 are greater than H2, then there does not exist an element in H2 that would violate the max heap property once inserted onto H1. Is there something I'm not taking into consideration?
If you maintain the heap balanced, it may be represented with an array, where the elements (2n+1) and (2n+2) are the leaves of the node (n).
In that case, you can't simply attach the root of H2 to an arbitrary leaf of H1.
> all I would have to do is insert all elements from H2 into H1
¿how do you do that insertion?
if you use the .insert() method of the heap for every element, you end with O(n2 lg n1) time.
Or you may append H2 to H1
> since every element in H1 is larger than every element in H2.
as long as n2<=n1+1 you would add only a single level. Consider what happen in the other case, and tell me if you can assure the heap property.
If you maintain the heap balanced, it may be represented with an array, where the elements (2n+1) and (2n+2) are the leaves of the node (n).
In that case, you can't simply attach the root of H2 to an arbitrary leaf of H1.
It occurs to me that if H1 is like 1000 -> 999 -> 998 -> 997, then as an array it could have as few as 0 + 1 + 3 + 7 = 10 free elements. If H2 has exactly 10 elements, then there may not be any way to add H2 to H1 in O(n2) time without reallocating the array.
Yes, but if H1 looks like [1000, null, 999, null, null, null, 998, null, null, null, null, null, null, null, 997], how could you merge an H2 heap with 10 elements into it in 10*k operations or less?
You could fill each null position with an element from H2, but that would take O(n1+n2). Compacting H1 would take O(n1). Reallocating to a larger array would take even longer.