Heap-Sort

5MB

PriorityQueues.pdf

pdf

We can use any priority queue to develop a sorting method. We insert all the keys to be sorted into a minimum-oriented priority queue, then repeatedly remove the minimum to remove them all in order. When using a heap for the priority queue, we obtain heapsort.

Focusing on sorting, we abandon the notion of hiding the heap representation of the priority queue and use swim() and sink() directly. Doing so allows us to sort an array without needing any extra space, by maintaining the heap within the array to be sorted. Heapsort breaks into two phases: heap construction, where we reorganize the original array into a heap, and the sortdown, where we pull the items out of the heap in decreasing order to build the sorted result.

• Heap construction. We can accomplish this task in time proportional to n lg n,by proceeding from left to right through the array or bottom-up method, using swim() to ensure that the entries to the left of the scanning pointer make up a heap-ordered complete tree, like successive priority queue insertions. A clever method that is much more efficient is to proceed from right to left, using sink() to make subheaps as we go. Every position in the array is the root of a small subheap; sink() works or such subheaps, as well. If the two children of a node are heaps, then calling sink() on that node makes the subtree rooted there a heap.

• Sortdown. Most of the work during heapsort is done during the second phase, where we remove the largest remaining items from the heap and put it into the array position vacated as the heap shrinks.

Max-PQ Heap Sort

#include <iostream>
using namespace std;

void sink(char *arr, int k, int n)
{
     while (k * 2 <= n)
     {
          int j = 2 * k;
          if (j < n && arr[j - 1] < arr[j])
               j++;
          if (!(arr[k - 1] < arr[j - 1]))
               break;

          swap(arr[k - 1], arr[j - 1]);
          k = j;
     }
}

void heapSort(char *arr, int size)
{
     int N = size;

     // Heap-Ordered
     for (int k = N / 2; k >= 1; k--)
          sink(arr, k, N);

     // Heap-Sort
     while (N > 1)
     {
          swap(arr[0], arr[--N]);
          sink(arr, 1, N);
     }
}

int main()
{
     char arr[] = {'S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
     int n = sizeof(arr) / sizeof(arr[0]);
     heapSort(arr, n);
     for (int i = 0; i < n; i++)
          cout << arr[i] << " ";
}

Proposition. Sink-based heap construction is linear time.

Proposition. Heapsort users fewer than 2 n lg n compare and exchanges to sort n items.

Most items reinserted into the heap during sortdown go all the way to the bottom. We can thus save time by avoiding the check for whether the item has reached its position, simply promoting the larger of the two children until the bottom is reached, then moving back up the heap to the proper position. This idea cuts the number of compares by a factor of 2 at the expense of extra bookkeeping.