We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements).
We know that the smallest element at $H_1$ is bigger the root (the biggest element) of $H_2$.
We want algorithm that makes one heap from both at $O(n_2)$.
My suggestion (at brief):
We have two cases:
- $n_1>n_2$ - At this case we have no problem at we take all the
elements of $H_2$ and put it on $H_1$. Why this will work? Lets say
that $H_1$ have $l_1$ leaves, so we know that: $$2l_1\ge n1 > n2$$
So if we put all the elements of $H_2$ at the leaves of $H_1$ and every new element of $H_2$ will be under element of $H_1$ (and because we know that every element of $H_1$ is bigger then every element of $H_2$ -> There is no problem! it's $O(n_2)$ - $n_2\ge n_1$ - At this case what we will do is this - we have to verify that all the elements at some level at the heap are bigger the then elements of level below.
How we doing it? We know that the root is the biggest element at $H_2$ and we look for smallest element at the leaves, and of course it's $O(n_2)$ because we look for a minimum at something that it's size is less then $n_2$.
After we those two elements we can use Counting Sort and after this sort we will put the elements of $H_2$ after $H_1$ - and this will be also $O(n_2)$...
Did I right? My proof is wrong? If yes - how can I fix it?
Thank you!