Heaps and the Heapsort Algorithm

Key Insight

A binary heap is an array-based data structure that can be visualized as a nearly complete binary tree. Each node in this tree corresponds to an element in the array, and the tree is filled completely at all levels except possibly the lowest, which is filled from left to right. An array 'A' representing a heap has two attributes: 'A.length' (total elements in the array) and 'A.heap_size' (number of valid heap elements). For a node at index 'i', its parent is 'floor(i/2)', its left child is '2i', and its right child is '2i + 1'.

Heaps come in two types: max-heaps and min-heaps, differentiated by their 'heap property'. In a max-heap, for any node 'i' other than the root, 'A[PARENT(i)] >= A[i]', meaning a node's value is at most its parent's, and the largest element resides at the root. Conversely, in a min-heap, 'A[PARENT(i)] <= A[i]', placing the smallest element at the root. The height of an 'n'-element heap is 'floor(log n)', and most basic heap operations, such as 'MAX-HEAPIFY', run in O(log n) time.

The heapsort algorithm sorts an array in-place in O(n log n) time. It consists of two main phases: first, `BUILD-MAX-HEAP` (O(n) time) converts the input array into a max-heap. Second, it iteratively extracts the maximum element (which is always at the root 'A[1]'). This is achieved by swapping 'A[1]' with 'A[A.heap_size]', decrementing 'A.heap_size', and then calling `MAX-HEAPIFY(A, 1)` to restore the max-heap property on the remaining elements. This process repeats until the heap size reduces to 1, leaving the array sorted.