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.
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.
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.
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.
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.
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.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic