**Heapsort** is one of the good general-purpose sort algorithms, part of the selection sort family.
The advantages of Heapsort are that it works in-place and the worst-case running time to sort *n* elements is O(*n* log *n*).
For reasonably large values of *n*, the log *n* term is almost constant, so that the sorting time is close to linear in the number of items to sort.

Because Heapsort requires only a fixed amount of extra storage space, it is a true in-place algorithm. The "siftdown" routine given below uses tail recursion which requires stack space in naive interpreters and compilers, but a good language implementation (such as any Scheme implementation) or a competent programmer can straightforwardly convert the algorithm to an iterative form.

Table of contents |

2 Explanation 3 Implementation |

To explain Heapsort, we will assume that we are sorting an array whose index values runs from 1 to *n*.
This will later be generalised to arbitrary index ranges.
Array elements *i* will be referred to as *a*[*i*].

Construct the heap by superimposing a binary tree structure on the array. Element *a*[*i*] is the parent of two children *a*[2*i*] and *a*[2*i*+1]. The heap property holds for index *i* if *a*[*i*] >= *a*[2*i*] and *a*[*i*] >= *a*[2*i*+1].

We need only one function to establish and maintain the heap. Suppose that the heap property holds for the indices *b*, *b*+1, ..., *e*. The sift-down function extends the heap property to *b*-1, *b*, *b*+1, ..., *e*.
Only index *i* = *b*-1 can violate the heap property.
Let *j* be the index of the largest child of *a*[*i*] within the range *b*, ..., *e*.
(If no such index exists because 2*i* > *e* then the heap property holds for the newly extended range and nothing needs to be done.)
By swapping the values *a*[*i*] and *a*[*j*] the heap property for position *i* is established.
The only problem now is that the heap property might not hold for index *j*.
The sift-down function is applied tail-recursively to index *j* until the whole heap property is established.

The sift-down function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log_{2} *e* steps are required.

The heapsort algorithm is now easy to explain.

- Given array
*a*[1, ...,*n*]. Let*i*:=floor(*n*/2)+1. The heap property holds for*a*[*i*, ...,*n*] because 2*i*>*n*so none of the elements in this range has a child. - Apply the sift-down function to positions
*i*-1,*i*-2, ..., 1. Each sift-down function extends the heap property by one index leftward until the entire array is a heap. - Set
*i*=*n*. - The largest (remaining) element is now at
*a*[1]. Swap*a*[1] and*a*[*i*] to put it in its correct place. The heap property still holds for*a*[2, ...,*i*-1]. Use sift-down to extend it to*a*[1, ...,*i*-1]. Subtract one from*i*, and repeat this step until the whole array is sorted.

Although not widely known, it is possible to define a ternary Heapsort. Instead of each element having two children, each element has three. Ternary Heapsort is somewhat more complicated to program, but it is potentially faster. Each step in a ternary heap requires three comparisons and one swap vs. two comparisons and one swap in a binary heap. 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.

Here's an implementation in the Java programming language:

This implementation does not contain any recursion (in order to make it faster) and expressions like i=i*2 have been replaced by i<<1 for better performances.

import java.util.Comparator; import java.util.Collections; import java.util.ArrayList; import java.util.List;public class HeapSort {

public static class DefaultComparator implements Comparator { public DefaultComparator() {} public int compare(Object a, Object b) { return ((Comparable)a).compareTo(b); } } public static void sort(Object[] A) { sort(A, new DefaultComparator()); } public static void sort(Object[] A, Comparator c) { ArrayList list = new ArrayList(A.length); for (int i=0; i

public static void sort(List A) { sort(A, new DefaultComparator()); }

public static void sort(List A, Comparator c) { int heapsize = A.size(); buildHeap(A, c); for (int i = heapsize; i>0; i--) { Collections.swap(A, 0, i-1); heapsize--; siftdown(A, 0, heapsize, c); } }

private static void buildHeap(List A, Comparator c){ int heapsize = A.size();

for (int i=heapsize/2; i>=0; i--){ siftdown(A, i, heapsize, c); } }

private static void siftdown(List A, int i, int heapsize, Comparator c){ int largest = i; // becomes the largest of A[i], A[2i], & A[2i+1] do { i = largest; int left = (i << 1) + 1; // left=2*i+1 int right = left + 1; if (left < heapsize){ largest = indexOfLargest(A, largest, left, c); if (right < heapsize) { largest = indexOfLargest(A, largest, right, c); } }

if (largest != i) { Collections.swap(A, i, largest); } } while (largest != i); }

private static int indexOfLargest(List A, int i, int j, Comparator c){ if ( c.compare(A.get(i), A.get(j)) < 0) { return j; } else { return i; } }

}