What is the fastest way (in theory at least) to sort a heap?

Question

A heap is a list where the following applies:

l[i] <= l[2*i] && l[i] <= [2*i+1]

for 0 <= i < len(list)

I'm looking for in-place sorting.

Answer 1

Read the items off the top of the heap one by one. Basically what you have then is heap sort.

Answer 2

Well you are half way through a Heap Sort already, by having your data in a heap. You just need to implement the second part of the heap sort algorithm. This should be faster than using quicksort on the heap array.

If you are feeling brave you could have a go at implementing smoothsort, which is faster than heapsort for nearly-sorted data.

Answer 3

Sorting a heap in-place kind of sounds like a job for Heap Sort.

I assume memory is constrained, an embedded app, perhaps?

Answer 4

Just use heap-sort. It is in-place. That would be the most natural choice.

You can as well just use your heap as it and sort it with some other algorithm. Afterwards you re-build your heap from the sorted list. Quicksort is a good candidate because you can be sure it won't run in the worst-case O(n²) order simply because your heap is already pre-sorted.

That may be faster if your compare-function is expensive. Heap-sort tend to evaluate the compare-function quite often.

Answer 5

Since you already have a heap, couldn't you just use the second phase of the heap sort? It works in place and should be nice and efficient.

Answer 6

For in-place sorting, the fastest way follows. Beware of off-by-one errors in my code. Note that this method gives a reversed sorted list which needs to be unreversed in the final step. If you use a max-heap, this problem goes away.

The general idea is a neat one: swap the smallest element (at index 0) with the last element in the heap, bubble that element down until the heap property is restored, shrink the size of the heap by one and repeat.

This isn't the absolute fastest way for non-in-place sorting as David Mackay demonstrates http://users.aims.ac.za/~mackay/sorting/sorting.html">here - you can do better by putting an element more likely to be the smallest at the top of the heap instead of one from the bottom row.

Time complexity is T(n.log n) worst case - n iterations with possibly log n (the height of the heap) goes through the while loop.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
 swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
 swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }