Data structure interview question
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?
"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?
Last edited on
It sounds to me that if you just pick any leaf of H1 and attach the root of H2, that you're done.
Last edited on
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.
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. |
however
¿or am I misunderstanding you?
| (assume that both H1 and H2 are large enough to hold n1 + n2 elements) |
¿or am I misunderstanding you?
Last edited on
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.
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.
when you use the array, you maintain the heap balanced.
the only <null> positions would be at the end, at most one node would have only one child.
the only <null> positions would be at the end, at most one node would have only one child.
Maybe it's one of those trick questions and it's easier than it seems.
Last edited on
Topic archived. No new replies allowed.