1
$\begingroup$

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time.

I've been having some difficulty in solving this problem. One thing I have thought of is traversing one of the trees using a tree traversal algorithm and adding each element to the other tree. The complexity for the traversal should be O(n) while adding to a binary tree is O(log n). One thing I'm not sure of is, would this method be O(n log n) or O(n) + O(log n)?

Another thought I had was to take the elements from the trees and put them into a sorted list. I would then create a binary tree from that list. Creating either a min or max-heap from a sorted list seems like it would be O(n) since insertions are O(1). Is that true or am I making an error in my thinking?

$\endgroup$
  • 6
    $\begingroup$ Hint: you can construct a heap with $n$ entries in time $O(n)$. $\endgroup$ – Raphael Mar 10 '16 at 0:48
  • $\begingroup$ If the trees are implemented via pointers, not as an array, it could even be done in time $O(\log n)$; with the usual array implementation, it can at least be done using only $O(\log n)$ comparisons. $\endgroup$ – chirlu Mar 10 '16 at 17:39
  • $\begingroup$ One thing I'm not sure of is, would this method be O(n log n) or O(n) + O(log n)? - $O(logn)$ is one addition. You make $n$ additions. So this is $O(nlogn)$ $\endgroup$ – Alaa M. Mar 11 '16 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.