14 votes 14 votes 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$. DS descriptive isi2014-pcb-cs algorithms binary-tree binary-heap + – go_editor asked May 31, 2016 go_editor 1.7k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Chhotu commented Oct 22, 2017 reply Follow Share 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. 0 votes 0 votes Rishabh Gupta 2 commented Jan 12, 2018 reply Follow Share @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). :) 4 votes 4 votes mahabir10 commented Dec 4, 2019 reply Follow Share 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). 0 votes 0 votes Please log in or register to add a comment.
Best answer 14 votes 14 votes 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/ debanjan sarkar answered May 31, 2016 • edited Jan 4, 2018 by kenzou debanjan sarkar comment Share Follow See 1 comment See all 1 1 comment reply `JEET commented Dec 4, 2019 reply Follow Share $\log n$ or $O(\log n)$? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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) rish1602 answered Aug 11, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.