A queue chooses the oldest waiting item. A priority queue chooses the most important item under a stated priority rule. A binary heap implements that rule by keeping an extreme priority at the root while maintaining a compact, shallow tree.
Reading route¶
Priority-queue behaviour: define selection, empty cases and ties.
Heap order, shape and array indices: connect a complete tree to its array representation.
Insertion and sift-up: append at the next leaf and repair one ancestor path.
Root removal and sift-down: preserve complete shape and choose the correct child.
Bottom-up heap construction: build in linear time rather than repeatedly inserting.
Python heaps and application records: attach payloads, resolve ties and handle changing priorities.
Heapsort, costs and choices: distinguish extraction from in-place sorting and compare heaps with search trees.
Review ADTs, dynamic arrays, tree terminology and sorting properties. AVL implementation is not a prerequisite, but the final comparison explains how their invariants support different operations.
The core follows the lecture’s min-heap [2, 5, 4, 9, 7, 6]. Teaching functions store finite numeric priorities, with constant-time comparisons and assignments assumed. Application examples separately attach records. No notebook is needed.
Consistent operation and implementation route¶
Each reading follows purpose/contract → representation and invariant → visual trace → implementation → choices/correctness → time/space → suitability → self-checks, adapted to the helper or algorithm it explains. Use the min-heap diagrams to trace repairs first; the record adapters and max-heap sorting code then change the interface or ordering rule explicitly.
| Layer | Return and mutation contract | What the code implements |
|---|---|---|
| Numeric list heap | Push returns None; peek observes a priority; pop removes and returns one | Min-heap sifts, push, peek, pop and copying bottom-up build |
| Record priority queue | Insert returns None; peek observes an item; remove/extract returns and removes it | Stable min queue and numeric-priority max adapter, size/empty and FIFO ties |
| Sorting | Return None and reorder the supplied list | Iterative max-heap heapsort, O(1) workspace and no stability promise |
The public min/max contract table separates entry count, duplicate payloads and empty behaviour. Record adapters delegate internal storage to heapq; numeric functions expose the repair mechanics. Bulk construction is shown for numeric priorities, not as an unimplemented method on the record class.
Arbitrary-item removal, indexed priority changes, automatic obsolete-entry cleanup and hard latency guarantees are not supplied by the small queue classes. Their conceptual strategies remain explained separately. The cost comparison counts resizing, output and key-operation assumptions explicitly.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.