Unit 4 · Heavy
Two structures that trade ordering for speed. Hashing gives constant average lookup by abandoning order entirely; a heap keeps only enough order to expose the extreme element.
What a strong answer looks like
A strong Unit 4 answer states the case and the assumption behind it, and never quotes constant time unconditionally.
Know
Constant average lookup depends on a hash function spreading keys evenly. With every key colliding the structure degrades to a list.
Apply
Use hashing when membership or lookup by key dominates and order does not matter.
Watch out
Quoting constant time without the even-distribution assumption, which makes the claim unfalsifiable.
Study move
Describe a key set that makes a plausible hash function perform badly.
Know
Chaining stores collisions in a secondary structure; probing finds another slot and suffers clustering. Load factor predicts how often collisions occur.
Apply
Compare the two strategies on memory and on graceful degradation as the table fills.
Watch out
Ignoring resizing, which is an amortised cost that explains the constant-time claim.
Study move
Insert colliding keys under both strategies and compare probe counts.
Know
The heap property constrains each parent against its own children only. That weaker ordering is why maintenance is logarithmic and the extreme sits at the root.
Apply
Use a heap when the extreme element is needed repeatedly but full sorting is not.
Watch out
Expecting sorted output from a heap. Only the root is guaranteed.
Study move
Draw a valid min-heap whose level order is visibly unsorted.
Know
A priority queue built on a heap is the engine behind Dijkstra, scheduling, and top-k selection.
Apply
For top-k over a stream, keep a heap of size k rather than sorting everything.
Watch out
Sorting an entire stream to find a few extremes, which is asymptotically worse and often infeasible.
Study move
Design a top-k selection over a large stream and state its cost per element.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
From a stream of millions of values, return the 10 largest, and state both the time per element and the total memory used.
