Heapsort and sorting via min-heaps

Question

I know how to sort-in-place an array using heapsort and max-heap property.
But I cannot think of how I could sort it in place using the min-heap property.

I can sort it using a min-heap by using a temporary intermediate array e.g.

public static int[] heapSort2(int[] array){
     buildMinHeap(array);
     int [] temp = new int[array.length];
     for(int i = 0; i < array.length; i++ ){
      temp[i] = extractMin(array);
      } 
   return temp;//returns array input sorted
}

But I can not think of a way to do it without using temp. Is it possible, or is min-heap only for priority queues?

Answer 1

Sorting in-place using a min-heap is symmetric to sorting with a max-heap.

Suppose that you're sorting with ascending order, and you have a max-heap array, with the root always in the first element (index 1), and you do one sorting step by moving the root out into the place of the last leaf (which is the rightmost element that is not yet sorted), making this leaf the new root and sinking it into the heap.

Then you sort with ascending order using a min-heap array by having the root always in the last element (index N), and you do one sorting step by moving the root out into the place of the last leaf (which is the leftmost element that is not yet sorted), making this leaf the new root and sinking it into the heap.

The equations for getting the indices of the parent, left and right children are different in such a heap. In the former case, assuming indices 1->N, the equations are:

parent(i) = floor(i / 2)
leftchild(i) = 2 * i
rightchild(i) = 2 * i + 1

In the latter, reversed min-heap case, the equations are obtained by reversing the indices at input and output of the above:

parent(i) = N + 1 - floor((N + 1 - i) / 2)
leftchild(i) = N + 1 - (2 * (N + 1 - i))
rightchild(i) = N + 1 - (2 * (N + 1 - i) + 1)

You can see that the latter equations look ugly compared to the former (but it may be possible to simplify them). Therefore, when sorting in ascending order, you're best off only using a max-heap, not a min-heap. Use a min-heap only when you want to sort in descending order - in the same orientation as you would use a max-heap when sorting in ascending order (root on first element).