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?