Heapsort (original) (raw)

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.

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(_n_2) 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_[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 log2 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.

For arrays that do not start at 1 the definition of the child index has to be adjusted. If an array starts with index value 0, then the children of _a_[_i_] are a_[2_i+1] and a_[2_i+2]. It is easy to verify that this imposes the same binary tree structure as the original definition on arrays starting at 1. Similar adaptations can be made for any other array range.

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.

Implementation

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<a.length; i++){="" list.add(a[i]);="" }="" sort(list,="" c);="" list.toarray(a);="" }<p="">

public static void sort(List A) { sort(A, new DefaultComparator()); }</a.length;>

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; } }

}