Binary Heaps & Priority Queues

Imagine you are running a hospital emergency room and patients keep arriving with different urgency levels. You always need to serve the most critical patient first. A priority queue solves this problem, and the binary heap is the data structure that makes it efficient. A heap is a special kind of binary tree stored cleverly in a simple array, where the most important element (highest priority) is always at the top. This week you will learn how heaps work, how to insert new elements and remove the top element in O(log n) time, and a surprising result — you can build a heap from scratch in just O(n) time, not O(n log n) as you might expect. You will also learn HeapSort, a sorting algorithm that uses heaps to achieve O(n log n) performance with no extra memory.

Learning Objectives

Understand the difference between max-heaps (parent is always larger than children) and min-heaps (parent is always smaller) and how they are stored as arrays

Implement the key operations: insert (add a new element and bubble it up), extract-max/min (remove the top and sift down), and heapify (fix a single violation)

Understand the surprising proof that build-heap runs in O(n) time, not O(n log n) — because most nodes are near the bottom where heapify is very cheap

Implement HeapSort, which builds a max-heap and repeatedly extracts the maximum to produce a sorted array in O(n log n) time with O(1) extra space

Key Concepts

Heap Property & Array Representation

A binary heap is a special type of binary tree (a tree where each node has at most two children) with two rules: (1) it is 'complete,' meaning every level is fully filled except possibly the last, which fills left to right, and (2) it satisfies the 'heap property.' In a max-heap, every parent node is greater than or equal to its children — so the largest element is always at the very top (the root). In a min-heap, every parent is less than or equal to its children, so the smallest is at the top. The clever trick is that this tree can be stored as a plain array with no pointers needed: for an element at index $i$ , its parent is at index $\lfloor(i-1)/2\rfloor$ , its left child is at $2i+1$ , and its right child is at $2i+2$ . This makes heaps very memory-efficient.

-
Max-heap rule: every parent is ≥ its children, so A[parent(i)] ≥ A[i] for all nodes — the maximum is always at the root (index 0)
-
Min-heap rule: every parent is ≤ its children, so A[parent(i)] ≤ A[i] for all nodes — the minimum is always at the root (index 0)
-
Because the tree is 'complete' (no gaps), it can be stored compactly in an array — no need for pointers like linked lists or regular trees
-
The height of a heap with n elements is ⌊log₂(n)⌋, which means operations that travel from root to leaf (or vice versa) take at most O(log n) steps

Heap Operations

There are two main operations on a heap. Insert: to add a new element, place it at the very end of the array (the next available spot in the bottom level of the tree), then 'bubble it up' — compare it with its parent and swap if it is larger (for max-heap) or smaller (for min-heap), repeating until the heap property is restored. Extract-max (or extract-min): to remove the top element, replace it with the last element in the array, then 'sift it down' — compare it with its children and swap with the larger (or smaller) child, repeating until it settles into the right position. Both operations travel at most from root to leaf or leaf to root, so they take $O(\log n)$ time — very fast even for millions of elements.

-
Insert: O(log n) — the new element bubbles up at most 'height' levels, and the height of the tree is log₂(n)
-
Extract-max: O(log n) — after replacing the root with the last element, it sifts down at most 'height' levels to find its correct position
-
maxHeapify (also called sift-down or downheapify): O(log n) — it restores the heap property for a subtree rooted at a given node by comparing with children and swapping downward

Build-Heap & HeapSort

Build-heap takes any unordered array and transforms it into a valid heap. Instead of inserting elements one by one (which would take O(n log n)), it uses a clever bottom-up approach: start from the last non-leaf node and call heapify on each node working upward to the root. Surprisingly, this takes only O(n) time — not O(n log n) — because the vast majority of nodes are near the bottom of the tree where heapify does very little work. HeapSort uses this idea to sort: first build a max-heap, then repeatedly swap the root (the maximum) with the last unsorted element and shrink the heap by one. After n-1 such swaps, the array is fully sorted. HeapSort runs in O(n log n) time and uses O(1) extra space, making it in-place and optimal, though it is not stable.

-
Build-heap is O(n), not O(n log n) — the key insight is that about half the nodes are leaves (which need no work), and the few nodes near the top that need more work are vastly outnumbered by the many cheap nodes near the bottom
-
HeapSort achieves O(n log n) in the worst case and is in-place (O(1) extra space), but it is not stable — equal elements may get reordered during the swap-and-heapify process
-
Heaps are the standard implementation for priority queues — any time you need fast access to the highest (or lowest) priority item, use a heap

W3: Searching & Selection W5: BSTs & Balanced Trees