ISI2014-PCB-CS-2b

Question

Let $H_1$ and $H_2$ be two complete binary trees that are heaps as well. Assume $H_1$ and $H_2$ are max-heaps, each of size $n$. Design and analyze an efficient algorithm to merge $H_1$ and $H_2$ to a new max-heap $H$ of size $2n$.

Comments

Hi @Rishabh Gupta,

I did one typo in my query. Please check now.

There's difference in both the questions

Could you please explain what is the exact difference ? It will be great help.

---

@Chhotu I got it now.

The difference is that in this question, both trees are individually complete. So, if we try to combine them as two subtrees, it is not necessary that the resulting tree will also be complete. But in the gate 2015 question, it is already given that the tree(combined) is complete. Clear?

If it was given that H1 and H2 are full with same number of nodes. Or H1 is full and H2 is complete having same depth, then we can do it in O(logn).

:)

---

I think the answer should be O(logn) because they have not mentioned anything about how the heaps are implemented. If it is implemented in array then it will take O(n) and its method is mentioned in selected answer. But if it is implemented through the linked list then we can merge both in O(logn) by making a new node and deleting the value of last element of one of the heaps and placing them in the new node and calling heapify() function on that node. Complexity of this procedure is O(logn) which is due to the max_heapify() procedure and making a node takes constsnt time and deleting the last node also takes constant time. So i believe the answer is O(logn).

Answer 1

First copy the two arrays of $H_1$ and $H_2$ into a new array of size $2n$...then apply build heap operation to get $H$...Time complexity$=O(2n)=O(n)$

http://www.geeksforgeeks.org/merge-two-binary-max-heaps/

Comments

$\log n$ or $O(\log n)$?

Answer 2

i think question is asking to build heap H such that the height of the combined heap is 2n. Then just merging is required and time complexity will be 0(n)