special minHeap, how to print all the n elements in O(n)?

Question

Speical minHeap is a minHeap which each level is sorted from left to right. How can I print all the n elements by order in O(n) at worst case?

The minHeap is implemented by binary heap, in which the tree is a complete binary tree (see figure).

here is the example of a special minHeap:

So the result should be: [1,3,4,5,8,10,17,18,20,22,25,30]

Question from homework.

Answer 1

If n is a parameter independent of the size of the heap, then under a standard comparison-based model, this is impossible. You will need additional restrictions, like more preexisting order than you've mentioned, or all elements of the heap being integers under a sufficiently low bound.

Suppose you have a heap of height k, where the root and its chain of left children have values 1, 2, 3, ... k. We can assign values >k to the k-1 right children of these nodes in any order without violating the "special minheap" condition, then assign values greater than those to fill out the rest of the heap. Printing the top 2k-1 values in this heap requires sorting k-1 values that could be in any order, which cannot be done through comparisons in less than O(k*log(k)) time.

---

If n is supposed to be the size of the heap, this is straightforward. The heap invariant is unnecessary; it only matters that the layers are sorted. A mergesort merging the first and second layers, then merging each successive layer into the already-merged results, will take O(n) time. The kth merge merges 2^k-1 already-merged elements with <=2^k elements from the next layer, taking O(2^k) time. There are O(log(n)) merges, and summing O(2^k) from k=1 to k=log(n) gives O(n).