Heapsort

Heapsort is one of the best general-purpose sort algorithms, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

Overview

One simple way to sort a list of objects is to use a heap data structure. We add all of our objects into the heap, and the heap organizes the elements added to it in such a way that we can quickly extract either the largest value (in a max-heap) or the smallest value (in a min-heap). Moreover, because this operation preserves the heap's structure, we can extract the largest/smallest value over and over again until none remain. This gives us the elements in order.

In doing so, the only extra space required is that needed to store the heap. In order to achieve constant space overhead, we use a trick: we store a binary heap (or alternatively, a heap with more than two children) inside the part of the input array which has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.) Heapsort makes use of two standard heap operations: insertion and root deletion. Each time we delete (extract) the maximum, we place it in the last location of the array not yet occupied, and use the remaining prefix of the array as a heap holding the remaining unsorted elements:

Variations

Although not widely known, it is possible to define a ternary heapsort which uses a ternary heap instead of a binary heap; that is, each element in the heap has three children. Ternary heapsort is somewhat more complicated to program, but it is potentially faster. Each step in the sift operation of a ternary heap requires three comparisons and one swap, whereas in a binary heap two comparisons and one swap are required. The ternary heap can do two steps in less time than the binary heap requires for three steps. But two steps of a ternary tree multiply the index by a factor of 9, which is more than the factor 8 of three binary steps. Ternary heapsort is about 12% faster than binary heapsort.

Comparison with other sorts

Heapsort primarily competes with quicksort, another very efficient general purpose nearly-in-place comparison-based sort algorithm.

Quicksort is typically somewhat faster, due to better cache behavior and other factors, but the worst-case running time for quicksort is O(n²), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem, and possible solutions.

The quicksort algorithm also requires Ω(log n) extra storage space, making it not a strictly in-place algorithm. This typically does not pose a problem except on the smallest embedded systems, or on systems where memory allocation is highly restricted. Constant space (in-place) variants of quicksort are possible to construct, but are rarely used in practice due to their extra complexity.

Thus, because of the O(n log n) upper bound on heapsort's running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heapsort.

Heapsort also competes with mergesort, which has the same time bounds, but requires Ω(n) auxilary space, whereas heapsort requires only a constant amount. Heapsort also typically runs more quickly in practice. However, mergesort is simpler to understand than heapsort, is a stable sort, parallelizes better, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Heapsort shares none of these benefits; in particular, it relies strongly on random access.

Implementation in pseudocode

The following is one way to implement the algorithm, in pseudocode, where swap is used to swap two elements of the array:

 function heapSort(a, count) {
     var int start := count ÷ 2, end := count - 1

     while start ≥ 0
         sift(a, start, count)
         start := start - 1

     while end ≥ 0
         swap(a[end], a[0])
         sift(a, 0, end)
         end := end - 1
 }
 
 function sift(a, start, count) {
     var int root := start, child

     while root * 2 < count {
         child := root * 2
         if child < count - 1 and a[child] < a[child + 1]
             child := child + 1
         if a[root] < a[child]
             swap(a[root], a[child])
             root := child
         else
             return
     }
 }

Implementation in C

This is a fast implementation of heapsort in C, adapted from Numerical Recipes in C but designed to be slightly more readable and to index from 0.

void heapsort(int arr[], int N)
{
  int n = N, i = n>>1, j, w, t;

  for (;;) {
    if (i>0)
      t = arr[--i];
    else {
      if (--n<=0) return;
      t = arr[n]; arr[n] = arr[0];
    }

    j = i;
    w = (i<<1)+1;

    while (w<n) {
      if (w+1<n && arr[w+1]>arr[w])
        ++w;
      if (arr[w]>t) {
        arr[j] = arr[w];
        j = w; w = (j<<1)+1;
      }
      else
        break;
    }
    arr[j] = t;
  }
}

External links

• Heapsort animated (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heapsort.html)
• Heapsort animated #2 (http://www2.hawaii.edu/~copley/665/HSApplet.html)
• NIST's Dictionary of Algorithms and Data Structures: Heapsort (http://www.nist.gov/dads/HTML/heapSort.html)
• Sorting revisited (http://www.azillionmonkeys.com/qed/sort.html)

de:Heapsort fr:Tri par tas ja:ヒープソート lt:Krūvos rūšiavimo algoritmas nl:Heapsort pl:Sortowanie_przez_kopcowanie pt:Heapsort zh:堆排序