Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?

Question

Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?

I've read a couple of answers and everyone says O(n) is the answer for this since we can put all the elements from both of the heaps into an array of size 2n and then run a build heap algorithm which takes O(n) time complexity.

But consider, this approach:

1. Take the last elements from both the heaps and determine which one is smallest and put it as a root of the new heap [ O(1)]
2. put the older heaps as the child of this new root.
3. Run a max heapify algorithm on this new heap [ O(logn) ]

Total T = O(1+logn) = O(logn)

I know that max heapify on a node X assumes that the nodes below X are already max heaps (which is satisfied already in the procedure I told above since both of the old heaps are max heaps by themselves. )

Where am I going wrong ?

Answer 1

(I assume your model of a heap is a binary tree, rather than an array).

One of the properties of a heap is that the bottom level is filled from left to right with no gaps. When you have two heaps of size n, their bottom levels are partially filled, so you can't conveniently join them into a single larger heap.

The mistake in your proof is that max heapify requires the nodes on the bottom level of the tree to be filled from left to right.

Note, there's no convenient way to adapt your idea to work in general. That's because there can be between 1 and n/2 nodes on the bottom level of each heap, and so you need to touch O(n) nodes to build the heap.