COMP9123 — Data Structures & Algorithms
Week 6: Maps, Priority Queues & Heaps
Week 6 compares abstract data types by what operations they promise, not by how they happen to be implemented. The lecture first frames maps as key-value storage, then narrows the interface to priority queues, and finally shows that heaps are the right structural compromise when you want fast inserts and fast remove-min together.
The big Week 6 question is not “what is a heap?” but “what workload are we optimizing for, and which invariants buy that speed?”
Map ADT: Key-Value Access as an Interface, Not a Structure
The lecture begins with the map ADT because it separates what users want from how the data is stored. A map promises lookup, insertion, replacement, and removal by key. It does not yet commit to lists, trees, hashes, or anything else.
| Map operation | Meaning | Why it matters |
|---|---|---|
get(k) |
Return the value associated with key k if it exists. |
The ADT is centered on key-based retrieval. |
put(k, v) |
Insert a new key-value pair or replace the old value for the same key. | Maps combine lookup and update in the same abstraction. |
remove(k) |
Delete the entry with key k if present. |
The structure must support dynamic change, not just search. |
entrySet(), keySet(), values() |
Iterate through stored associations. | The lecture is reminding you that a map is also a collection, not only a query interface. |
Unsorted list map
Very cheap to append or insert, but expensive for repeated key lookups because the whole list may need to be scanned.
When it is still useful
The slides explicitly call out small maps or append-heavy scenarios like logs, where fast insertion matters more than fast search.
Why the ADT framing matters
Next week, hashing will be another map implementation. The abstraction lets you compare them fairly.
Sorted Maps: Extra Order Gives Extra Queries
A plain map only cares about matching a key exactly. A sorted map does more because the keys live in a total order. That extra structure unlocks operations like first key, last key, floor, ceiling, predecessor, successor, and submap queries.
| Sorted-map method | Question it answers | What plain unsorted maps cannot do efficiently |
|---|---|---|
firstEntry(), lastEntry() |
What is the smallest or largest stored key? | Without order, you'd need a full scan. |
floorEntry(k), ceilingEntry(k) |
Which key is just below or just above the target? | These are inherently order-based queries. |
subMap(k1, k2) |
Which entries lie inside a key interval? | This is the map analogue of BST range queries. |
The lecture uses AVL trees as the natural sorted-map implementation because Week 5 already gave you logarithmic search on ordered keys. Week 6 is connecting that older tree material to a more general ADT story.
Priority Queue ADT: Deliberately Less General Than a Map
A priority queue also stores key-value items, but the interface is much narrower. You are not allowed arbitrary key lookup. The only privileged key is the smallest one, because many algorithms only ever need “give me the next most urgent item.”
| Priority-queue operation | Meaning | Algorithmic use |
|---|---|---|
insert(k, v) |
Add a new item with priority key k. |
Tasks, events, candidates, and frontier nodes enter dynamically. |
min() |
Peek at the smallest key without removing it. | Useful when you need to inspect the current best choice. |
remove_min() |
Remove and return the smallest-key item. | This is the central operation in greedy methods and shortest-path algorithms. |
Why the restriction is useful
By promising only what many algorithms actually need, the structure can be optimized around that one extreme element instead of arbitrary search.
Lecture application
The stock-matching example uses two priority queues at once: one for best buy offers and one for best sell offers.
Professor lens: good ADT design often means refusing to promise operations you do not need. A priority queue is powerful precisely because it is narrower than a full map.
Sequence Trade-offs: Unsorted List, Sorted List, and the Sorting Analogy
Before heaps appear, the lecture compares two simple sequence implementations of a priority queue. This is not filler. It trains the exact design instinct the heap is supposed to solve.
| Implementation | Insert | min() / remove_min() |
Best when... |
|---|---|---|---|
| Unsorted list | \(O(1)\) | \(O(n)\) | You insert constantly and rarely remove the minimum. |
| Sorted list | \(O(n)\) | \(O(1)\) | You want the smallest item ready immediately. |
| Heap | \(O(\log n)\) | \(O(\log n)\) for remove_min() |
You want neither side of the trade-off to become terrible. |
Selection-sort viewpoint
An unsorted-list priority queue mirrors the logic of selection sort: cheap insertion, expensive repeated extract-min.
Insertion-sort viewpoint
A sorted-list priority queue mirrors insertion sort: expensive insertion into a maintained order, cheap removal from the front.
Why this matters
The heap will be introduced as the balanced middle ground rather than a magical totally-best structure.
min() and remove_min() cheap by paying the price during insertion?Heap Structure: The Right Local Invariants for Global Remove-Min
A min-heap is defined by two invariants together, not one. Heap order alone is not enough, and tree shape alone is not enough. The lecture needs both to make the data structure fast.
| Heap invariant | Meaning | What it buys |
|---|---|---|
| Heap-order property | Every non-root node has key at least as large as its parent's key. | The global minimum must be at the root. |
| Complete binary tree property | All levels are full except possibly the last, which is filled left to right. | The height stays \(O(\log n)\), and the array representation becomes possible. |
Insert
Add the new node at the next available complete-tree position, then restore order by bubbling upward.
Upheap
Swap with the parent while the new key is smaller. Only one ancestor path is ever touched.
Remove-min
Move the last node to the root, delete the old last position, then repair the violated order by moving downward.
Each repair step swaps only along a single vertical path, never across the whole tree.
A complete binary tree with \(n\) nodes has height \(O(\log n)\).
So the number of swaps is bounded by the height, giving \(O(\log n)\) total time.
Array Heaps: Completeness Turns Pointers into Formulas
Once the tree is always complete, you no longer need explicit pointers to navigate the structure. The array position already tells you where the parent and children must be.
0-based heap indexing from the slides
root index = 0 last index = n - 1 left child(i) = 2i + 1 right child(i) = 2i + 2 parent(i) = floor((i - 1) / 2)
These formulas are not arbitrary memorisation. They are the arithmetic shadow of the complete-tree shape.
Build-heap refinement
The lecture notes that a heap can be built from an unsorted array in \(O(n)\) time using a bottom-up strategy, even though \(n\) repeated insertions would cost \(O(n \log n)\).
Comparator warning
The code and slides both remind you that ordering may come from a comparator, not just numeric keys. Good implementations should not assume comparisons return only \(-1, 0, 1\).
The patient-triage example at the end of the lecture is there to show that the key itself can be composite, like severity first and age as a tiebreaker. Once you understand that, heaps stop being toy integer structures and become a real modelling tool.
Tutorial & Code: Move Between By-Hand Heap Work and Algorithm Design
Tutorial 6 starts with heap fundamentals, then quickly broadens into analysis and heap-powered algorithms. You are expected to be comfortable both with manual heapify steps and with using a priority queue as a subroutine in larger problems.
| Tutorial / code item | Main idea it is testing | Why it matters |
|---|---|---|
| Warm-up 1 | Check whether an array really is a valid heap | You need to verify both structure and order, not just spot the largest or smallest value. |
| Warm-up 2 | Explain why build-heap is linear | This is the lecture's first “surprising but true” heap analysis. |
| Problem 6 | Use a heap to find the \(k\)-th smallest in \(O(n \log k)\) | The structure becomes an algorithmic tool, not just a stored collection. |
| Problem 7 | Merge \(k\) sorted lists with a min-heap | This is the standard pattern for repeated “next smallest among many streams.” |
What the code bundle is trying to make you implement
class Node():
def up_heap(self): ...
def down_heap(self): ...
class PriorityQueue():
def insert(self, k, v): ...
def min(self): ...
def remove_min(self): ...
The split across priority_queue_list.py, priority_queue_heap.py, and node.py is intentional. The course wants you to compare whole-queue trade-offs while also understanding the tiny local swap logic that makes heap repair work.
Best Week 6 checkpoint: you should be able to explain why a heap is not just a sorted array in disguise, and why that partial order is exactly what makes it efficient.
Quiz Hub & Revision Targets
Use practice tools after the ADT comparison is already clear in your head. If you cannot yet explain when you would choose an unsorted list, a sorted list, or a heap, then more drilling on operations alone will not stick.
You should be able to explain
How maps, sorted maps, and priority queues differ in the operations they promise and why those promises shape implementation choice.
You should be able to distinguish
Heap order from full sorting, and complete-tree structure from BST ordering.
You should be able to design
A heap-based solution for a repeated “next smallest” problem such as merging sorted lists or processing tasks by urgency.
Suggested sequence: finish the foundations page next for the index formulas and build-heap reasoning, then come back for mixed practice once the trade-off table feels natural.