Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A heap sorted by levels is a heap which:
Every parent is smaller than its children.
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)$.
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)$.
