Getting the sorted sequence from a level-wise sorted min-heap

A heap sorted by levels is a heap which:

1. Every parent is smaller than its children.

2. The nodes in each level are sorted from the smallest to the greatest.

I need to describe an algorithm with $O(n)$ runtime that prints the values in the heap in sorted order.

I only manage to do it in $O(n \log(\log n))$ using another heap but have no idea of how to do it in $O(n)$.

• Is it 1. means that parent with value $P$ can have child with value $C$ such that $P > C$ (i.e. parent is bigger that child)? Commented Jul 19, 2015 at 22:33
• 1. What does "smaller than is 1/2 children's" mean? Can you edit to rephrase that sentence? 2. What have you tried? What approaches have you considered? We discourage bare problem statements that just ask us to solve your exercise/problem for you. 3. Please edit to improve the title.
– D.W.
Commented Jul 20, 2015 at 2:32
• I think "1/2 children" meant "all of the children, of which there may be one or two". I edited thus. Is that what you wanted to state, Yoav? (cc @D.W.) Commented Jul 20, 2015 at 6:38

Use a recursive algorithm. Suppose the heap has depth $D$. Recursively compute a sorted list of all the numbers in the top $D-1$ levels (i.e., all but the bottom level); let $L$ be this list. Let $L'$ be the list of numbers in the bottom level. Note that both $L$ and $L'$ are in sorted order, so we can use the Merge procedure from Mergesort to compute a sorted list of all of the numbers.
If you work out the recurrence relation, you'll see that the running time of this algorithm is $O(n)$. Indeed, Merge runs in $cn$ time, for some constant $c$, so the total running time will be $cn + cn/2 + cn/4 + \dots \le 2cn = O(n)$.