Heapsort: short notes (Algorithms)

Introduction

Heapsort sorts an array by first arranging it into a max-heap and then repeatedly moving the maximum to the end. It is the only standard comparison sort that is both in place ( $O(1)$ auxiliary space) and guaranteed $O(n \lg n)$ in the worst case. Its weaknesses are that it is not stable, not adaptive, and usually slower in practice than quicksort because its memory accesses jump around the array.

The heap itself (shape and heap properties, the array layout, MAX-HEAPIFY, BUILD-MAX-HEAP and why building is $\Theta(n)$ ) is covered in Binary Heaps. This note uses those results and concentrates on heapsort as a sorting algorithm: its trace, its exact cost, its properties, and the selection problems it solves.

Prerequisites

Binary Heaps: 1-based array layout (children of $i$ at $2i$ and $2i + 1$ ), MAX-HEAPIFY in $O(h)$ , BUILD-MAX-HEAP in $\Theta(n)$ .
Elementary Sorting: stability, in-place and adaptive sorting.

The algorithm

Purpose. Sort $A[1..n]$ into non-decreasing order in place. Input. $A[1..n]$ . Output. The same array, sorted.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$ .

Text

HEAPSORT(A, n)
    BUILD-MAX-HEAP(A, n)               // Theta(n); see Binary Heaps
    for i <- n downto 2
        exchange A[1] with A[i]         // current maximum to its final place
        A.size <- A.size - 1            // A[i..n] is now outside the heap
        MAX-HEAPIFY(A, 1)               // restore the heap on A[1..i-1]

Loop invariant. At the start of the iteration for index $i$ :

$A[1..i]$ is a max-heap containing the $i$ smallest elements of the input.
$A[i+1..n]$ contains the $n - i$ largest elements, in sorted order.

The exchange puts the largest of the $i$ heap elements at position $i$ , which extends part 2; MAX-HEAPIFY restores part 1 on the smaller heap $A[1..i-1]$ (its precondition holds because only the root changed). When the loop ends at $i = 1$ , the single remaining element is the minimum, so the whole array is sorted.

Descending order. Use a min-heap instead (MIN-HEAPIFY, BUILD-MIN-HEAP); the minimum moves to the end each time, so the array ends in non-increasing order.

Worked example

Input $A = [5, 13, 2, 25, 7, 17, 20, 8, 4]$ , $n = 9$ . The Binary Heaps note traces BUILD-MAX-HEAP on this input; it produces the heap $25, 13, 20, 8, 7, 17, 2, 5, 4$ after 5 exchanges.

The sorting phase then runs $i = 9, 8, \ldots, 2$ . In the table, the part after the bar is outside the heap and already in final position.

$i$	Root moved to $A[i]$	Array after exchange and MAX-HEAPIFY	Sift-down exchanges
9	25	20 13 17 8 7 4 2 5 \| 25	2
8	20	17 13 5 8 7 4 2 \| 20 25	1
7	17	13 8 5 2 7 4 \| 17 20 25	2
6	13	8 7 5 2 4 \| 13 17 20 25	2
5	8	7 4 5 2 \| 8 13 17 20 25	1
4	7	5 4 2 \| 7 8 13 17 20 25	1
3	5	4 2 \| 5 7 8 13 17 20 25	1
2	4	2 \| 4 5 7 8 13 17 20 25	0

Result: $2, 4, 5, 7, 8, 13, 17, 20, 25$ . The sorting phase made 10 sift-down exchanges and 22 key comparisons (MAX-HEAPIFY compares with each existing child, up to two comparisons per level).

Look at the first row in detail. After exchanging 25 with $A[9] = 4$ , the heap $A[1..8]$ has 4 at the root. Its children are 13 and 20, so 4 is exchanged with 20 (index 3). The children of index 3 are now 17 (index 6) and 2 (index 7), so 4 is exchanged with 17. Index 6 has no children inside the heap of size 8, so the sift-down stops.

Heapsort extract-max passes on the example heap — Figure 1. The sorting phase of heapsort on the heap 25 13 20 8 7 17 2 5 4: an initial heap panel followed by eight extraction panels, each extraction showing the heap as a tree and as an array after the exchange and sift-down for $i = 9$ down to 2, with the sorted suffix shaded and the sift-down path marked.

Analysis

Time

BUILD-MAX-HEAP: $\Theta(n)$ (proof in Binary Heaps).
The loop runs $n - 1$ times; each MAX-HEAPIFY on a heap of $i - 1$ elements costs $O(\lg i)$ . Total $O(\sum_{i=2}^{n} \lg i) = O(\lg(n!)) = O(n \lg n)$ .

So heapsort is $O(n \lg n)$ in the worst case. For inputs with distinct keys it is also $\Omega(n \lg n)$ (the matching best-case bound for distinct keys is a known but harder result), so its time is $\Theta(n \lg n)$ on every input of distinct keys, including already sorted input. It is not adaptive.

Case	Time	Remark
Worst	$\Theta(n \lg n)$	at most about $2n \lg n$ key comparisons with the two-comparison MAX-HEAPIFY
Average	$\Theta(n \lg n)$
Best, distinct keys	$\Theta(n \lg n)$	sorted or reverse-sorted input does not help
Best, all keys equal	$\Theta(n)$	every MAX-HEAPIFY stops at once (no child is strictly larger)

A reverse-sorted array ( $n, n-1, \ldots, 1$ ) is already a max-heap, so BUILD-MAX-HEAP makes no exchanges, but the sorting phase still costs $\Theta(n \lg n)$ .

Space

MAX-HEAPIFY written as a loop (instead of tail recursion) needs $O(1)$ extra space, and the heap occupies the input array. Heapsort is therefore in place with $O(1)$ auxiliary space. With the recursive MAX-HEAPIFY as written in CLRS, the stack can reach $O(\lg n)$ frames; this is a property of that implementation, not of the algorithm.

Stability

Heapsort is not stable. The smallest example has two equal keys: for $1_a, 1_b$ , the array is already a max-heap ( $1_b$ is not larger than $1_a$ ), and the first exchange of $A[1]$ with $A[2]$ produces $1_b, 1_a$ . The long-distance exchanges between the root and the end of the heap reorder equal keys in general. Binary Heaps gives a three-element example.

Properties

Property	Heapsort
Worst-case time	$\Theta(n \lg n)$
Auxiliary space	$O(1)$ (iterative sift-down)
In place	yes
Stable	no
Adaptive	no
Comparison-based	yes, asymptotically optimal
Online	no (needs all elements before the first output in sorted order)

Compared with quicksort and merge sort.

Against quicksort: heapsort's worst case is $O(n \lg n)$ instead of $\Theta(n^2)$ , but its average constant is larger and its access pattern (jumping between $i$ and $2i$ ) is unfriendly to caches. Introsort uses quicksort and falls back to heapsort when the recursion becomes too deep.
Against merge sort: heapsort needs no $\Theta(n)$ buffer, but merge sort is stable and works well on linked lists and external data.

Fewer comparisons. The "bottom-up" variant of heapsort first sifts the hole down to a leaf along the path of larger children (one comparison per level), then moves the displaced key back up. This cuts the comparisons of the sorting phase to about $n \lg n$ on average.

Where elements can sit in a max-heap

Consider where the minimum, or the $k$ -th largest, can be in a max-heap of $n$ distinct keys (1-based).

Minimum. It has no larger descendant to be above, so it has no children: it is a leaf, in one of the positions $\lfloor n/2 \rfloor + 1, \ldots, n$ . Finding it takes $\lceil n/2 \rceil - 1$ comparisons, a scan of the leaves; the heap order does not help beyond halving the search.
Second largest. For $n\ge3$ , compare the children at positions 2 and 3. For $n=2$ , choose position 2 without a comparison; for $n<2$ , the statistic is undefined.
$k$ -th largest. Every ancestor of a key is larger than it, so the $k$ -th largest has at most $k - 1$ ancestors and lies at depth at most $k - 1$ , in positions 1 to $2^k - 1$ . For $k \ge 2$ it is never at the root.

In the example heap $25, 13, 20, 8, 7, 17, 2, 5, 4$ : the leaves are positions 5 to 9 (keys 7, 17, 2, 5, 4) and the minimum 2 is at position 7; the second largest, 20, is at position 3; the third largest, 17, is at position 6, depth 2 ( $\le k - 1 = 2$ ). Note that the leaves hold 17, the third largest, so "the leaves hold the smallest keys" is false.

Selection with heaps

Related material. Heap-based selection is not a separate item of the GATE syllabus. It is included because it is commonly studied together with heaps and heapsort.

Heaps also solve "find the $k$ largest" without sorting everything.

Problem	Method	Time	Extra space
$k$ largest of $n$ (array given)	build a max-heap, extract $k$ times	$O(n + k \lg n)$	$O(1)$ in place
$k$ largest of a stream	keep a min-heap of the $k$ largest seen; replace its root when a larger element arrives	$O(n \lg(k+1))$	$O(k)$
$k$ -th smallest	min-heap and $k$ extract-mins, or a max-heap of size $k$	$O(n + k \lg n)$ or $O(n \lg(k+1))$
Partial sort of the top $k$	stop after $\min(k,n-1)$ extraction rounds; if $k=n$ , the final remaining root is already in place; the last $k$ positions hold them in order	$O(n + k \lg n)$	$O(1)$

The selection bounds above assume $1\le k\le n$ . For $k=1$ , the streaming method takes $O(n)$ ; selecting zero elements needs no heap.

For a single order statistic, quickselect is expected $\Theta(n)$ with distinct keys for the displayed Lomuto version, or with equality-aware partitioning for duplicates; heaps win when $k$ is small or the data arrives as a stream.

Edge cases

$n \le 1$ : BUILD-MAX-HEAP does nothing and the loop does not run.
$n = 2$ : one exchange in the loop, possibly after one exchange in the build.
Equal keys: the algorithm is correct; stability is lost.
0-based arrays: children at $2i + 1$ and $2i + 2$ , parent at $\lfloor (i - 1)/2 \rfloor$ ; the loop runs $i = n - 1$ down to 1.

Important properties and observations

After $k$ iterations of the sorting loop, the last $k$ positions hold the $k$ largest elements in sorted order, and $A[1]$ is the largest of the rest.
The sorting phase dominates: $\Theta(n)$ to build, $\Theta(n \lg n)$ to sort (for distinct keys).
The total number of exchanges is at most the build exchanges plus $(n - 1)$ root exchanges plus $\sum_i \lfloor \lg(i - 1) \rfloor$ sift-down exchanges.
"Heapsort on sorted input with distinct keys is $O(n)$ " is false; "heapsort is stable" is false; "heapsort needs $O(n)$ extra space" is false.

GATE examination perspective

Intermediate arrays. the array after BUILD-MAX-HEAP, or after the first $k$ iterations of the sorting loop. Trace each sift-down level by level and keep track of the shrinking heap size.
Counting. the number of exchanges or comparisons for a small input; state whether build-phase operations are included.
Properties. in place, not stable, $\Theta(n \lg n)$ worst case, not adaptive.
Selection. $k$ largest in $O(n + k \lg n)$ with a max-heap; streaming top $k$ with a min-heap of size $k$ .
Positions. in a max-heap the minimum is a leaf (positions $\lfloor n/2 \rfloor + 1$ to $n$ ); the $k$ -th largest is at depth at most $k - 1$ .

Summary

Binary Heaps: prerequisite. Heap operations and the $\Theta(n)$ build.
Quicksort: related. Faster on average; heapsort is its worst-case fallback in introsort.
Merge Sort: related. Stable $\Theta(n \lg n)$ alternative with a $\Theta(n)$ buffer.
Comparison of Sorting Algorithms: dependent. Heapsort in the full comparison table.

Heapsort

Introduction

Prerequisites

The algorithm

Worked example

Analysis

Time

Space

Stability

Properties

Where elements can sit in a max-heap

Selection with heaps

Edge cases

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

The algorithm

Worked example

Analysis

Time

Space

Stability

Properties

Where elements can sit in a max-heap

Selection with heaps

Edge cases

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps