Heapsort

From Wikipedia, the free encyclopedia

A run of the heapsort algorithm sorting an array of randomly permutated values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and 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. Heapsort is an in-place algorithm and is not a stable sort.

1 Overview
2 Variations
3 Comparison with other sorts
4 Pseudocode
5 Pseudocode
6 C-code
7 References
8 See also
9 External links

[edit] Overview

One simple way to sort a list of objects is to use a heap data structure. All elements to be sorted are inserted into a heap, and the heap organizes the elements added to it in such a way that either the largest value (in a max-heap) or the smallest value (in a min-heap) can be quickly extracted. Moreover, because this operation preserves the heap's structure, the largest/smallest value can be repeatedly extracted 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:

Heap of remaining unsorted elements

Sorted elements

[edit] Variations

The most important variation to the simple variante is an improvement by R.W.Floyd which gives in practise about 25% speed improvement by using only one comparision in each siftup run which then needs to be followed by a siftdown for the original child; moreover it is eleganter to formulate. Heapsort's natural way of indexing works on indices from 1 up to the number of items. Therefore the start address of the data should be shifted such that this logic can be implemented avoiding unnecessary +/- 1 offsets in the coded algorithm.

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 shift 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 the simple variante of binary heapsort.

The smoothsort sorting algorithm is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O(n log n). The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. Due to its complexity, smoothsort is rarely used.

[edit] 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 merge sort, which has the same time bounds, but requires Ω(n) auxiliary space, whereas heapsort requires only a constant amount. Heapsort also typically runs more quickly in practice on machines with small or slow data caches. On the other hand, merge sort has several advantages over heapsort:

Like quicksort, merge sort on arrays has considerably better data cache performance, often outperforming heapsort on a modern desktop PC, because it accesses the elements in order.
Merge sort is a stable sort.
Merge sort parallelises better; the most trivial way of parallelising merge sort achieves close to linear speedup, while there is no obvious way to parallelise heapsort at all.
Merge sort 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 relies strongly on random access, and its poor locality of reference makes it very slow on media with long access times.

[edit] Pseudocode

The following is the "simple" way to implement the algorithm, in pseudocode, where swap is used to swap two elements of the array. Notice that the arrays are zero based in this example.

 function heapSort(a, count) {
     var int start := count ÷ 2 - 1,
     var int 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                     % Point to a root node
     var int child

     while root * 2 + 1 < count {              % While the root has child(ren)...
         child := root * 2 + 1                 % ... point to its left child
         % If the child has a sibling and the child's value is less than its sibling's...
         if child < count - 1 and a[child] < a[child + 1]
             child := child + 1                % ... point to the right child instead
         if a[root] < a[child]                 % If the value in root is less than in child...
             swap(a[root], a[child])           % ... swap the values in root and child and...
             root := child                     % ... make root point to its child
         else
             return
     }
 }

[edit] Pseudocode

The strange thing about the above implementation is that it uses heapify-down operations to achieve what we really want to achieve using heapify-up operations. Imagine building the heap. As we add new elements, we want them to crawl up the heap. For the actual sorting, however, the standard implementation jibes with intuition. The following implementation jibes completely with intuition and is still O(n log n).

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

     while start ≤ count - 2
         start := start + 1
         siftup(a, start)

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

     while root * 2 + 1 < count {
         child := root * 2 + 1
         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
     }
 }
 
 function siftup(a, start) {
     var int child := start, root, remainder

     while child > 0 {
         remainder := (child - 1) % 2
         root := ((child - 1) - remainder) / 2 
         if a[root] < a[child]
             swap(a[root], a[child])
             child := root
         else
             return
     }
 }

[edit] C-code

It follows an implementation of the "standard"-heapsort, also called buttom-up-heapsort. It is faster on average (see Knuth. Sec. 5.2.3, Ex. 18) and even better in worst-case behaviour (1.5n log n) than the simple heapsort (2n log n). The sift_in routine is first a sift_up of the free position followed by a sift_down of the new item. The needed data-comparision is only in the macro data_i_LESS_THAN_ for easy adaption.

/*  Heapsort based on ideas of J.W.Williams/R.W.Floyd/S.Carlsson  */

#define  data_i_LESS_THAN_(other)   (data[i] < other)
#define  MOVE_i_TO_free  { data[free]=data[i];  free=i; }

void sift_in(unsigned count, SORTTYPE *data, unsigned free, SORTTYPE next)
{
   unsigned  i;
   /** sift up the free node **/ 
   for (i=2*free;i<count;i+=i)
   {  if (data_i_LESS_THAN_(data[i+1]))  i++;
      MOVE_i_TO_free
   }
   /* special case in sift up if the last inner node has only 1 child */
   if (i==count)
      MOVE_i_TO_free
   /** sift down the new item next **/
   while((i=free/2)  &&  data_i_LESS_THAN_(next))
      MOVE_i_TO_free
   data[free] = next;
}

void heapsort(unsigned count, SORTTYPE *data)
{
   unsigned  j;
 
   if (count <= 1)  return;
   data-=1;   /* map addresses to indices 1 til count  */
   /** build the heap structure **/ 
   for(j=count/2;j;j-=1)
   {  SORTTYPE  next = data[j];
      sift_in(count, data, j, next);
   }
   /** search next by next remaining extremal element **/
   for(j=count-1;j;j-=1)
   {  SORTTYPE  next = data[j+1];
      data[j+1] = data[1];   /* extract extremal element from the heap */
      sift_in(j, data, 1, next);
   }
}

[edit] References

J. W. J. Williams. Algorithm 232 - Heapsort, 1964, Communications of the ACM 7(6): 347–348.
Robert W. Floyd. Algorithm 245 - Treesort 3, 1964, Communications of the ACM 7(12): 701.
Svante Carlsson, Average-case results on heapsort, 1987, BIT 27(1): 2-17.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 144–155 of section 5.2.3: Sorting by Selection.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapters 6 and 7 Respectively: Heapsort and Priority Queues
A PDF of Dijkstra's original paper on Smoothsort