# Merging two binary heaps in linear time

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?

• Hint: you can construct a heap with $n$ entries in time $O(n)$. – Raphael Mar 10 '16 at 0:48
• 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. – chirlu Mar 10 '16 at 17:39
• 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)$ – Alaa M. Mar 11 '16 at 16:43