Heapsort is a sorting algorithm that organizes elements into a binary heap, repeatedly removes the largest element, and places it at the end of the remaining unsorted portion. Its standard array-based implementation sorts in place, uses constant auxiliary storage, and has worst-case running time . Unlike quicksort, its worst-case bound does not depend on choosing favorable pivots. Standard heapsort is not stable: elements with equal keys may change their relative order.
Heap structure
A binary heap is a data structure with two properties:
- Shape: it is a complete binary tree, with every level full except possibly the last, which is filled from left to right.
- Heap order: in a max-heap, each parent's key is at least as large as the keys of its children.
The root of a max-heap therefore contains a largest element, although the remaining elements are not necessarily in sorted order. A min-heap reverses the ordering condition and places a smallest element at the root.
A complete binary tree can be represented compactly in an array without storing explicit pointers. With zero-based indexing, the children of position are at
provided those indices are within the active heap. For , its parent is at
This representation allows heapsort to keep both the active heap and the sorted output in the original array. For ascending order, the usual implementation uses a max-heap; for descending order, it can use a min-heap.
Algorithm
Heapsort has two phases.
Building the heap
The input array is first rearranged into a max-heap. The standard bottom-up construction visits all internal nodes in reverse index order, starting at
and ending at the root.
At each node, a sift-down operation restores heap order in the subtree rooted there. It compares the current element with its larger child. If the child is larger, the two elements are exchanged, and the operation continues downward. When a node is processed during bottom-up construction, both of its child subtrees are already heaps.
Leaves need no processing because a single-element subtree automatically satisfies heap order.
Repeated extraction
After heap construction, the largest element is at index . The algorithm:
- Exchanges the root with the last element of the active heap.
- Shrinks the active heap by one element.
- Sifts the new root downward to restore heap order.
- Repeats until at most one element remains in the heap.
The array is thus divided into an active heap on the left and a sorted suffix on the right. Each extraction adds the largest remaining element to the beginning of that suffix.
Pseudocode
The following pseudocode sorts in ascending order. The parameter size is the number of elements in the active heap, so valid heap indices are strictly less than size.
procedure sift_down(A, root, size):
while 2 * root + 1 < size:
child = 2 * root + 1
if child + 1 < size and A[child] < A[child + 1]:
child = child + 1
if A[root] >= A[child]:
return
swap A[root], A[child]
root = child
procedure heapsort(A):
n = length(A)
for start = floor(n / 2) - 1 downto 0:
sift_down(A, start, n)
for end = n - 1 downto 1:
swap A[0], A[end]
sift_down(A, 0, end)
A loop whose starting index is below its ending bound performs no iterations. Consequently, this algorithm also handles empty arrays and single-element arrays without special sorting steps.
Implementations can reduce assignments by holding the displaced element in a temporary variable, moving larger children upward, and writing the displaced element only once at its final position.
Example
Consider the array
[4, 10, 3, 5, 1]
Bottom-up heap construction produces
[10, 5, 3, 4, 1]
Successive extractions and heap repairs produce the following states. The vertical bar separates the active heap from the sorted suffix.
[5, 4, 3, 1 | 10]
[4, 1, 3 | 5, 10]
[3, 1 | 4, 5, 10]
[1 | 3, 4, 5, 10]
The completed array is
[1, 3, 4, 5, 10]
The intermediate heap portions are not sorted sequences; only the heap-order condition is maintained.
Correctness
The extraction phase can be explained through a loop invariant. Before each extraction:
- The active prefix is a max-heap.
- The suffix is sorted in ascending order.
- Every element in the active heap is no greater than every element in the suffix.
The root is a largest element of the active heap. Exchanging it with the last active element therefore places the next-largest remaining element immediately before the existing sorted suffix.
Only the replacement root can violate heap order: its child subtrees have not changed internally. Sift-down repairs that violation while leaving the suffix untouched. When the active heap has at most one element, the entire array is sorted.
This reasoning assumes comparisons define a consistent ordering. Inconsistent comparison functions can invalidate both the heap property and the sortedness guarantee.
Complexity
Linear-time heap construction
A single sift-down may take time, but applying that upper bound independently to every node gives an unnecessarily loose bound for bottom-up construction.
Most nodes lie near the leaves and can move only a short distance. The number of nodes of height decreases geometrically, so the total work is bounded by a sum of the form
Thus bottom-up heap construction takes time. Constructing a heap by inserting elements individually has an worst-case bound instead.
Sorting time
There are extractions, and each requires at most work. The resulting worst-case time complexity is
For random permutations of distinct keys, the usual implementation also has expected running time . As a comparison sort, heapsort is subject to the general worst-case comparison lower bound for sorting distinct keys.
Best-case behavior depends on the precise implementation and assumptions about keys. In the early-stopping sift-down shown above, an array of equal keys takes time: each heap repair stops immediately. It is therefore misleading to describe every heapsort implementation as taking on every possible input. Nevertheless, heapsort is generally not adaptive to existing sorted order.
Auxiliary storage
With iterative sift-down, the auxiliary space complexity is , excluding the input array. The heap is stored directly in that array, and only a few indices and temporary values are needed.
An implementation using recursive sift-down can require call-stack space.
Stability and ordering
A stable sort preserves the original relative order of records with equal sorting keys. Standard heapsort does not have this property because its long-distance exchanges can move equal-key records past one another.
For example, two records with the same key can exchange relative positions when one is moved from the root to the end of the active heap.
Stability can be imposed by comparing each record using the pair
but storing original positions generally requires additional storage unless that information is already available. This changes the storage characteristics of the overall method rather than making ordinary heapsort intrinsically stable.
Heapsort requires only comparisons, not arithmetic on keys. It can therefore sort records, strings, or other objects under a suitable comparator. Its usual complexity bounds assume comparisons and element moves have constant cost; expensive comparisons or large records can substantially affect actual running time.
Practical performance and applications
Heapsort is useful when both a worst-case bound and low auxiliary memory are important. Its storage requirements do not grow with input size when implemented iteratively.
Its practical limitations include:
- Memory locality. Sift-down follows parent-to-child paths with increasingly large index jumps. These accesses often make less effective use of the CPU cache than sequential scans.
- Comparison and movement costs. Each level commonly requires selecting the larger child and then comparing that child with the displaced element.
- Limited adaptivity. Already sorted or nearly sorted inputs generally do not lead to the improvements available from adaptive sorting methods.
- Instability. Applications requiring stable ordering need a different algorithm or additional machinery.
Performance depends on hardware, key distributions, comparison costs, and implementation details. Heapsort often runs more slowly than well-engineered quicksort-based methods despite offering a stronger worst-case guarantee than basic quicksort.
A prominent application is introsort, which begins with quicksort-style partitioning and switches to heapsort when partitioning becomes too deep. This retains much of quicksort's typical performance while preventing quadratic worst-case behavior.
The underlying heap operations also support a priority queue. However, heapsort is specifically an array-sorting procedure: repeatedly removing items from a separately allocated priority queue is related, but does not necessarily have the same in-place storage properties.
Comparison with related algorithms
| Algorithm | Worst-case time | Typical auxiliary storage | Stable in its standard form? |
|---|---|---|---|
| Heapsort | with iterative sift-down | No | |
| Quicksort | Typically expected stack space; implementation-dependent | No | |
| [[merge-sort | Merge sort]] | Usually for array-based implementations | |
| [[insertion-sort | Insertion sort]] |
Merge sort combines stability with predictable running time, but conventional array implementations require a temporary buffer. Insertion sort is useful for small or nearly sorted inputs. Heapsort's distinctive combination is worst-case time and constant auxiliary storage.
History and variants
J. W. J. Williams introduced heapsort in 1964. Robert W. Floyd published an improved heap-construction method in the same year. Floyd's bottom-up construction establishes the heap in linear time and is standard in modern presentations.
Variants alter the heap structure or the repair procedure:
- Bottom-up heapsort variants can descend along a path of larger children before locating the displaced element's final position, reducing comparisons in some settings. This extraction strategy is distinct from bottom-up heap construction.
- -ary heapsort gives each node up to children. A larger branching factor reduces heap height but increases the work required to select a largest child.
- Partial heapsort performs only enough extractions to obtain a requested number of largest elements. Building a max-heap and extracting elements takes time, although the extracted elements accumulate at the array's end rather than sorting the entire input.