Searching and sorting · 16 / 53
Heaps, priority queues and heapsort
Understand → trace → implement → justify
2 min reading · allow extra time for practiceA binary heap preserves completeness and heap order. In a min-heap, each parent is no larger than its children; entire left/right subtrees need not be ordered like a BST. Array children are 2i+1 and2i+2; parent is (i−1)//2.
Insertion appends and sifts up; removing the minimum replaces the root with the final item and sifts down. Arbitrary-key lookup may be O(n). Decrease-key needs position tracking; heapq-based algorithms often tolerate stale entries and discard them later.
Bottom-up heapify is Θ(n) because most nodes are near leaves. Heapsort repeatedly moves a max-heap root to the end. Its in-place form uses O(1) auxiliary storage and is not stable. Tie-breakers avoid unintended comparisons between payload objects.
A worked trace
Insert1 into [2,5,3]: append, swap with5, then2, yielding [1,2,3,5].
Cost and assumptions
peek O(1), push/pop O(log n), heapify Θ(n), heapsort Θ(n log n).
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
import heapq
jobs = [(3, "C"), (1, "A"), (2, "B")]
heapq.heapify(jobs)
order = [heapq.heappop(jobs)[1] for _ in range(3)]
assert order == ["A", "B", "C"]TEST YOUR UNDERSTANDING
Your turn
Is the entire heap array sorted?
Reveal the reasoning
No. [1,4,2] is a valid min-heap but not a sorted array. Only parent-child order and the root minimum are guaranteed.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
MIT 6.006 · Introduction to Algorithms ↗