This chapter introduces heapsort, a comparison-based sorting algorithm that combines the best attributes of merge sort and insertion sort: it runs in O(n lg n) time like merge sort, yet sorts in place like insertion sort. The chapter also introduces the heap data structure—a nearly complete binary tree stored as an array—which is not only the engine behind heapsort but also the foundation for an efficient priority queue implementation used extensively in later chapters (e.g., Dijkstra's algorithm, Prim's MST).
A (binary) heap is an array that can be viewed as a nearly complete binary tree. The tree is completely filled on all levels except possibly the lowest, which is filled from the left.
An array A representing a heap has two attributes:
A.length — total number of elements in the array.
A.heap-size — how many elements in A[1..A.heap-size] are valid heap elements (≤ A.length).
Navigating the tree is done with simple index arithmetic (1-based indexing):
PARENT(i) = ⌊i/2⌋
LEFT(i) = 2i
RIGHT(i) = 2i + 1
These can be computed in one instruction via bit-shifting, making them extremely fast.
Max-heap property: For every node i other than the root, A[PARENT(i)] ≥ A[i]. The largest element is at the root.
Min-heap property: For every node i other than the root, A[PARENT(i)] ≤ A[i]. The smallest element is at the root.
Height of a node is the number of edges on the longest downward path to a leaf. The height of an n-element heap is ⌊lg n⌋.
Leaves occupy indices ⌊n/2⌋ + 1, ⌊n/2⌋ + 2, …, n (Exercise 6.1-7), which is important for BUILD-MAX-HEAP.
i are already max-heaps, but A[i] may be smaller than its children.