1
$\begingroup$

enter image description here 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)$.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – knok16 Jul 19 '15 at 22:33
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 20 '15 at 2:32
  • $\begingroup$ 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.) $\endgroup$ – Raphael Jul 20 '15 at 6:38
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.