Core · Module 11
Heaps and priority queues
Always know the smallest (or largest) item, using a tree stored in an array.
A priority queue always hands out the most urgent item next, and a binary heap implements it with nothing but an array: a complete tree whose parents and children are found by arithmetic. This module covers the heap property and its array layout, the sift-up and sift-down operations, building a heap in linear time and sorting with it, and the patterns that make heaps indispensable: top k, k-way merging and running medians.
- 1The heap property in an arrayPro — members onlyA priority queue always hands out its smallest (or largest) item next. A binary heap implements it as a complete tree stored in a plain array, where parents and children are found by arithmetic instead of pointers.13 min
- 2Sift-up and sift-downPro — members onlyA heap inserts by appending at the end and swapping upward, and removes the minimum by moving the last item to the root and swapping downward. Each walks one path, so both are O(log n).14 min
- 3Heapify and heap sortPro — members onlyBuilding a heap by sifting down from the last parent to the root takes O(n), not O(n log n), because most nodes sit near the bottom. Repeatedly moving the maximum to the end then sorts the array in place.14 min
- 4Top-k and merging streamsPro — members onlyA heap of just k items finds the k largest of a billion in one pass. A heap of k stream heads merges k sorted streams. Two heaps keep a running median. These three patterns cover most heap problems.15 min