Chapter 6: Heapsort: Heaps, Priority Queues, and the Heapsort Algorithm

A heap is a nearly complete binary tree stored compactly in an array, where parent-child relationships are computed through index arithmetic rather than pointers, and it comes in two forms: a max-heap, where every parent is greater than or equal to its children with the maximum at the root, and a min-heap, where the minimum sits at the root — both having height Θ(log n). The core maintenance operation, MAX-HEAPIFY, restores the heap property at a given node by swapping it with its largest child and recursing downward, running in O(log n) time. Building a max-heap from an unordered array is accomplished by calling MAX-HEAPIFY bottom-up on every non-leaf node, and while each individual call costs O(log n), the total cost is only O(n) because the majority of nodes reside near the bottom of the tree and require little work. Heapsort leverages this by first building a max-heap, then repeatedly swapping the root — the current maximum — with the last element, shrinking the heap, and restoring the heap property, sorting the array in place with a worst-case running time of Θ(n log n). Beyond sorting, heaps provide a natural implementation of priority queues, supporting INSERT, MAXIMUM, EXTRACT-MAX, and INCREASE-KEY operations all in O(log n) time, with handles used to maintain the correspondence between elements and their positions in the heap — making the heap one of the most versatile and practically useful data structures in the book.