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 |
Heapsort vs. Quicksort
Heapsort primarily competes with Quicksort, another efficient nearly-in-place comparison-based sort algorithm.
Quicksort is typically somewhat faster, but the worst-case running time for Quicksort is O(n2) which becomes unacceptable for large data sets.
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.
Obscure constant-space variations on Quicksort exist but are never used in practice due to their extra complexity.
In situations where very limited extra storage space is available, Heapsort is the sorting algorithm of choice.
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 often use Heapsort.
Explanation
Heapsort works by first finding the largest element in the array, putting it in the last position, finding the next largest element, putting that in the next-to-last position, etc. A naive implementation of this idea would result in selection sort. Heapsort is more efficient because it uses a data structure called a heap.
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[2i] and a[2i+1]. The heap property holds for index i if a[i] >= a[2i] and a[i] >= a[2i+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 2i > 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 log2 e steps are required.
The heapsort algorithm is now easy to explain.
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.
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, 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;
}
}
}
Implementation
import java.util.Comparator;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;