Heapsort

Lore & Background

Heapsort was invented by J. W. J. The paper also introduced the binary heap as a useful data structure in its own right. In the same year, Robert W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm. The algorithm can be divided into two phases: heap construction and heap extraction. The heap is an implicit data structure that takes no space beyond the array of objects to be sorted; the array is interpreted as a complete binary tree where each array element is a node and each node's parent and child links are defined by simple arithmetic on the array indexes.

Reader's Guide

Heapsort's significance lies in its guaranteed O(n log n) worst-case runtime, making it a reliable fallback for quicksort variants that may become degenerate. Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate. The algorithm is in-place but not stable. Its heart is the siftDown() function, which constructs binary heaps out of smaller heaps or repairs a damaged heap. The heapify() operation runs once in O(n) time, and siftDown() is called n times with O(log n) work each, yielding overall O(n log n) performance. Heapsort's legacy includes the binary heap data structure, which remains widely used in priority queues and other applications.

Did You Know?

• Robert W. Floyd published an improved in-place version of heapsort in the same year.
• The algorithm is not a stable sort.
• Most real-world quicksort variants include heapsort as a fallback to avoid degenerate behavior.

The Architecture of a Heap

A heap is fundamentally a tree-based data structure governed by a single ordering rule: every parent node must hold a key that is at least as large (in a max heap) or at most as large (in a min heap) as the key of any of its children. The node sitting at the very top, with no parent above it, is called the root, and it always carries the highest-priority value in a max heap or the lowest in a min heap. Crucially, a heap is not a fully sorted structure. There is no guaranteed ordering between siblings, between cousins, or along any in-order traversal path the way a binary search tree would impose. The only constraint that matters runs vertically—between a node and its ancestors. This partial ordering is what makes the heap so efficient for its intended purpose: repeatedly surfacing the single most or least important element while allowing insertions and removals to be interleaved freely. Because of this, heaps are often used as the underlying implementation of priority queues, and in practice the two terms are frequently used interchangeably regardless of the actual implementation details.

Origins and Structural Efficiency

The binary heap, the most widely recognized variant of this data structure, was introduced by J. W. J. Its defining geometric property is that it forms a complete binary tree, meaning every level is fully populated except possibly the last, which is filled from left to right. This completeness guarantees the smallest possible height for a given number of nodes: a heap holding N nodes with a branches per node always has a height of log_a N. That logarithmic depth is what keeps every fundamental operation—insertion, extraction, sifting—bounded to logarithmic time in the worst case. Beyond sorting, the heap's structural efficiency makes it indispensable in several important graph algorithms, most notably Dijkstra's shortest-path algorithm, where the ability to quickly extract the minimum-distance node while updating distances is central to the method's performance.

The Operational Vocabulary

Working with a heap involves a rich set of operations organized around a few core ideas. At the most basic level, one can peek at the root to find the maximum or minimum without removing it, insert a new key by placing it at the first available position and sifting it upward until the heap property is restored, or extract the root by pulling it out, dropping the last element into the root position, and sifting that element downward. A particularly efficient operation is replacement, which removes the root and immediately inserts a new key in its place, requiring only a single sift-down rather than the two separate balancing passes that a pop-then-push sequence would demand. More advanced operations include merging two heaps into one, either preserving the originals as in a union or destroying them as in a meld, updating an existing key in place, and deleting an arbitrary node by moving the last element into its slot and sifting to restore order. The entire construction of a heap from an unsorted array can be accomplished in linear time using Floyd's classic algorithm, with the worst-case comparison count for a binary heap expressed as 2N minus a correction term involving the binary representation of N.

The Array Implementation and Memory Economy

Rather than allocating separate node objects with pointer links, a heap is typically stored directly in a plain array, with the parent-child relationships encoded implicitly through index arithmetic. In a zero-based binary heap, the root occupies index 0, its two children sit at indices 1 and 2, and in general a node at index i has children at 2i+1 and 2i+2, while its parent lives at floor((i−1)/2). In a one-based variant the formulas shift to 2i, 2i+1, and floor(i/2). This compact indexing scheme makes walking up or down the tree a matter of simple integer arithmetic, with no pointer chasing. Because no extra memory is needed beyond the array that already holds the keys, heapsort can sort an array entirely in place—a property that distinguishes it from other structures with comparable or even better theoretical bounds, such as radix trees, which do require auxiliary storage. After any insertion or deletion that disturbs the heap property, the structure is repaired by swapping out-of-order elements through the sift-up or sift-down procedure, restoring the invariant in logarithmic time.