DSA in 30 Days, Episode 7: Heaps, Priority Queues, Hashing and Collisions
Home / DSA series / Episode 7
Last updated: October 12, 2026
A college help desk has two different problems. It must pick the most urgent pending job, and it must find a student's record by roll number. A heap fits the first problem. A hash table fits the second. Neither replaces the other.
This is a general BTech CSE lesson, not an official university syllabus. Check your course outline for the required depth.
Matching video: the link will be added when available. The written lesson is below.
By the end, you should be able to trace a min-heap insertion and deletion, use a priority queue without breaking ties accidentally, resolve a hash collision, and explain when constant-time lookup is only an expectation.
Previous: Episode 6: trees, BST, AVL and LCA | Next: Episode 8: graphs | All episodes
What is a binary heap?
A binary heap is a complete binary tree: every level except possibly the last is full, and the last level fills from left to right. In a min-heap, a parent is no larger than either child. Therefore the root is the minimum. In a max-heap the comparisons reverse, and the root is the maximum.
The word complete describes the shape. The heap invariant describes the values. Both matter. A heap is not a binary search tree: the left and right subtrees have no BST ordering rule. It is also not a fully sorted array.
With zero-based array indexing, a node at index i has children at 2*i+1 and 2*i+2, when those indices exist. For a non-root node its parent is (i-1)//2. Appending to the array fills the next position in the complete tree.
Connect array indices to the tree
Array index: 0 1 2 3 4
Value: 5 10 30 20 15
0:5
/ \
1:10 2:30
/ \
3:20 4:15
Parent of index 4: (4-1)//2 = 1
Children of index 1: 3 and 4The indices explain the shape; the values explain the min-heap invariant. A sibling pair such as 10 and 30 need not be sorted. Only existing children are checked.
Trace insertion and removal
Insert 20, 15, 30, 5 and 10 into an empty min-heap. Append each value, then swap it upward while it is smaller than its parent. The states below were generated by the same code shown later.
| Inserted value | Heap array |
|---|---|
| 20 | [20] |
| 15 | [15, 20] |
| 30 | [15, 20, 30] |
| 5 | [5, 15, 30, 20] |
| 10 | [5, 10, 30, 20, 15] |
The final array is [5, 10, 30, 20, 15]. The root is 5, but 30 appears before 20. That is valid: only parent-child ordering is required.
5
/ \
10 30
/ \
20 15To remove the minimum, save the root, move the last value to the root and remove the last array position. Then swap downward with the smaller child until the invariant holds. Here 15 replaces 5, swaps with 10 and stops, giving [10, 15, 30, 20].
Choose the smaller child in a min-heap. Swapping with whichever child you notice first can leave the other child smaller than the new parent.
Run a small min-heap implementation
This version uses integers, keeps duplicates, mutates the given list and raises IndexError when asked to remove from an empty heap. It shows the mechanics rather than hiding them behind a library.
def push(heap, value):
heap.append(value)
child = len(heap) - 1
while child > 0:
parent = (child - 1) // 2
if heap[parent] <= heap[child]:
break
heap[parent], heap[child] = heap[child], heap[parent]
child = parent
def pop_min(heap):
if not heap:
raise IndexError('empty heap')
result = heap[0]
last = heap.pop()
if heap:
heap[0] = last
parent = 0
while 2 * parent + 1 < len(heap):
child = 2 * parent + 1
right = child + 1
if right < len(heap) and heap[right] < heap[child]:
child = right
if heap[parent] <= heap[child]:
break
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
return result
heap = []
for value in [20, 15, 30, 5, 10]:
push(heap, value)
print(heap)
print(pop_min(heap))
print(heap)
print([pop_min(heap) for _ in range(len(heap))])
Checked output:
[5, 10, 30, 20, 15]
5
[10, 15, 30, 20]
[10, 15, 20, 30]
The last output is sorted because repeated minimum removals sort the values. The heap array itself was never required to be sorted. The array-based binary-heap operations use O(log n) comparisons in the worst case for insertion and removal. Dynamic array growth can occasionally add a separate resizing cost to an insertion.
Why and where use a priority queue?
A priority queue is an interface: insert an item and remove the item with the best priority. A binary heap is one way to implement it. Use it when the next item depends on urgency or a score, rather than ordinary arrival order: a job queue, repeated smallest-value selection, or a graph algorithm's frontier.
Here a smaller priority number means more urgent. Python's heapq is a min-heap interface. Use a sequence counter to preserve arrival order between equal priorities. The counter also prevents Python from trying to compare the payload objects when priorities tie.
import heapq
from itertools import count
jobs = []
sequence = count()
for priority, name in [(2, 'lab report'), (1, 'exam form'),
(1, 'fee receipt'), (3, 'club poster')]:
heapq.heappush(jobs, (priority, next(sequence), name))
while jobs:
priority, arrival, name = heapq.heappop(jobs)
print(priority, name)
Checked output:
1 exam form
1 fee receipt
2 lab report
3 club poster
The two priority-1 jobs leave in their arrival order. Without the counter, a tuple containing only priority and a name would use the name as a tie-breaker, which is a different policy. A heap does not promise first-in-first-out behavior for ties by itself.
Heap costs and the heapify trap
| Operation | Binary-heap cost | Reason |
|---|---|---|
| Read root minimum | O(1) | The root is at index 0 |
| Insert / remove minimum | O(log n) | A value follows one tree path; array growth is separate |
| Search an arbitrary value | O(n) | Heap order does not choose one search subtree |
| Build by bottom-up heapify | O(n) | Most nodes are close to the leaves |
| Sort by repeated removals | O(n log n) | Each removal may follow a tree path |
Inserting n values separately has O(n log n) worst-case heap work. Bottom-up construction is O(n): start at the last internal node and sift each node downward. Many nodes require no movement, fewer can move one level, and still fewer can move several levels. Multiplying n by the full height charges every node for work it cannot do.
heapq.heapify(values) builds a min-heap in place. Do not call heappush on an arbitrary unheapified list and assume it repairs every old element. The push operation assumes the existing list already satisfies the invariant.
What is hashing?
A hash table maps a key to a candidate bucket or slot, then checks the stored key. For this lesson use integer keys and the toy rule h(key) = key % 7. This is useful for tracing, not a universal production hash function.
Same bucket does not mean same key. Keys 10, 17 and 24 all map to bucket 3. That is a collision, not evidence that the records are identical. A correct table must keep checking equality.
Two common collision strategies are separate chaining and open addressing. Chaining keeps a collection of entries in each bucket. Open addressing keeps entries in the table array itself and searches other slots according to a probe rule.
Resolve a collision by separate chaining
For keys 10, 17, 24 and 8, bucket 3 contains 10, 17 and 24; bucket 1 contains 8. This integer-key map updates an existing key rather than adding a duplicate. It deliberately has fixed capacity so the collision behavior stays visible.
class IntMap:
def __init__(self, capacity=7):
if capacity <= 0:
raise ValueError('capacity must be positive')
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def put(self, key, value):
bucket = self.buckets[key % len(self.buckets)]
for i, (stored_key, _) in enumerate(bucket):
if stored_key == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
def get(self, key):
for stored_key, value in self.buckets[key % len(self.buckets)]:
if stored_key == key:
return value
raise KeyError(key)
def delete(self, key):
bucket = self.buckets[key % len(self.buckets)]
for i, (stored_key, _) in enumerate(bucket):
if stored_key == key:
bucket.pop(i)
self.size -= 1
return
raise KeyError(key)
records = IntMap()
for key, value in [(10, 'Asha'), (17, 'Bilal'), (24, 'Charu'), (8, 'Dev')]:
records.put(key, value)
print(records.buckets[3])
print(records.get(17))
records.put(17, 'Bilal updated')
print(records.size, records.get(17))
records.delete(10)
print(records.buckets[3])
Checked output:
[(10, 'Asha'), (17, 'Bilal'), (24, 'Charu')]
Bilal
4 Bilal updated
[(17, 'Bilal updated'), (24, 'Charu')]
Looking up 17 scans its bucket until the stored key is 17. Updating it keeps the size at 4. Deleting 10 removes just that key, not the whole bucket. The demonstration is not Python's dict implementation and does not resize; use the built-in mapping for normal application work.
Resolve the same keys by linear probing
With an initially empty seven-slot table, try the home slot, then the next slot, wrapping around with modulo arithmetic. Insert the same keys in the same order:
| Key | Home slot | Slots examined | Final slot |
|---|---|---|---|
| 10 | 3 | 3 | 3 |
| 17 | 3 | 3, 4 | 4 |
| 24 | 3 | 3, 4, 5 | 5 |
| 8 | 1 | 1 | 1 |
| Slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Value | empty | 8 | empty | 10 | 17 | 24 | empty |
Searching for 24 starts at slot 3, checks 10 and 17, then finds 24 at slot 5. Searching for missing 31 visits slots 3, 4, 5 and the empty slot 6. In this no-deletion example an empty slot ends the search.
Deletion needs more care. If you simply make slot 3 empty after deleting 10, a later search may stop there and incorrectly claim 24 is absent. One solution is a tombstone marker that means continue searching; another is to repair the affected cluster. A full open-addressed implementation must also bound probes and handle a full table.
Linear probing can form clusters of occupied slots. It is simple and cache-friendly, but a long cluster makes later operations do more work.
See why deletion needs a marker
Chaining before deletion:
bucket 3 -> (10,Asha) -> (17,Bilal) -> (24,Charu)
bucket 1 -> (8,Dev)
Linear probing after deleting 10:
slot: 0 1 2 3 4 5 6
value: EMPTY 8 EMPTY DEL 17 24 EMPTY
find 24: home 3 -> DEL -> 17 -> 24 (found)
find 31: home 3 -> DEL -> 17 -> 24 -> EMPTY (absent)
Wrong: making slot 3 EMPTY hides keys at 4 and 5.DEL is not a stored key and is not an empty stopping point. A tombstone preserves the probe path. A production table also tracks tombstone buildup and rebuilds when needed. The IntMap code above uses chaining, so it does not need tombstones.
| Property | Separate chaining | Linear probing |
|---|---|---|
| Where entries live | Lists in buckets | Slots in one array |
| Collision handling | Compare keys within bucket | Probe later slots, wrapping around |
| Deletion | Remove matching pair | Keep a tombstone or repair cluster |
| Load factor | Can exceed 1 | Needs spare slots for efficient searches |
| Bad case | Long bucket | Long cluster |
Load factor: when is O(1) a fair claim?
The load factor is alpha = number of stored entries / number of buckets or slots. Our four distinct keys in seven positions give 4/7, about 0.57. Updating key 17 does not increase this number.
For separate chaining, expected lookup cost is O(1 + alpha) under a hash function that spreads keys well. With a bounded load factor, this is O(1) expected time. A bad hash function can send every key to one bucket, giving O(n) lookup in that bucket.
Open addressing needs spare slots; operations get more expensive as the table fills. Chaining can have alpha greater than 1 because a bucket may store several entries. These facts are different, so do not apply one universal load-factor limit to every table design.
Resizing allocates a larger table and redistributes entries according to the new capacity. One resize costs O(n) work, even when an implementation gives expected amortized O(1) insertion over a long sequence. Expected, worst-case and amortized costs answer different questions.
Choose the structure before choosing the code
| Question | Useful structure | What it does not promise |
|---|---|---|
| Which job has the best priority now? | Heap / priority queue | Fast arbitrary-key search |
| Which record belongs to this key? | Hash table | Sorted order or range queries |
| Which keys fall in this ordered range? | Balanced search tree | Constant-time lookup for every operation |
A hash table is not a cryptographic hash and is not an encryption system. Here hashing is a way to locate candidate storage positions. Security uses of hashes are a separate topic.
Run the invariant checks yourself
Run this after the push, pop_min and IntMap definitions. It checks every length-0-to-6 heap input over {-2, 0, 2}, then mixed insert/remove sequences and map operations whose keys all collide in bucket 3. Each sequence has 80 operations. Sorting and a Python dict provide independent references. These are finite tests, not a proof for all inputs.
# Run after push, pop_min and IntMap definitions.
from itertools import product
from random import Random
heap_cases = 0
for length in range(7):
for values in product((-2, 0, 2), repeat=length):
heap = []
for value in values:
push(heap, value)
assert all(heap[(i-1)//2] <= heap[i]
for i in range(1, len(heap)))
assert [pop_min(heap) for _ in values] == sorted(values)
try:
pop_min(heap)
except IndexError:
pass
else:
raise AssertionError('empty pop must fail')
heap_cases += 1
rng = Random(7)
for _ in range(500):
heap, reference = [], []
for step in range(80):
if not reference or rng.randrange(2) == 0:
value = rng.randrange(-30, 31)
push(heap, value)
reference.append(value)
else:
expected = min(reference)
assert pop_min(heap) == expected
reference.remove(expected)
assert sorted(heap) == sorted(reference)
assert all(heap[(i-1)//2] <= heap[i]
for i in range(1, len(heap)))
for _ in range(200):
records, reference = IntMap(), {}
for step in range(80):
# All keys collide in bucket 3, including negative keys.
key = 7 * rng.randrange(-5, 6) + 3
operation = rng.randrange(3)
if operation == 0:
records.put(key, step)
reference[key] = step
elif operation == 1:
try:
result = records.get(key)
except KeyError:
assert key not in reference
else:
assert result == reference[key]
else:
try:
records.delete(key)
except KeyError:
assert key not in reference
else:
del reference[key]
assert records.size == len(reference)
assert dict(pair for bucket in records.buckets
for pair in bucket) == reference
for capacity in (0, -1):
try:
IntMap(capacity)
except ValueError:
pass
else:
raise AssertionError('bad capacity must fail')
print('Exhaustive heap inputs:', heap_cases)
print('Mixed heap sequences: 500')
print('Colliding map sequences: 200')
print('Empty-pop and capacity errors passed')Executed output:
Exhaustive heap inputs: 1093
Mixed heap sequences: 500
Colliding map sequences: 200
Empty-pop and capacity errors passedExam answers
| Question | Answer |
|---|---|
| Is a heap a sorted array? | No. Parent-child order does not sort siblings or unrelated nodes. |
| Is a priority queue the same as a heap? | No. It is an interface; a binary heap is one implementation. |
| Why does deletion use the last node? | It preserves the complete-tree shape before sifting down. |
| Why choose the smaller child? | Choosing the other child could leave a smaller child below the new parent. |
| Why use a sequence counter? | It preserves arrival order for ties and avoids comparing payloads. |
| Does a collision mean equal keys? | No. Compare stored keys before updating or returning a value. |
| Does an update increase load factor? | No, not when it replaces the value of an existing key. |
| Why can chaining have alpha greater than 1? | A bucket can hold several entries. |
| Is hash lookup always O(1)? | No. Expected constant time requires suitable distribution and controlled load. |
| Why is heapify O(n), not O(n log n)? | Most nodes can move only a short distance; leaves do not move. |
Practice with checked answers
- Insert 12, 7, 25 and 3 into an empty min-heap using the shown code, then remove the minimum.
- With the seven-slot linear-probing table above, how many slots does a search for 31 examine?
- Using chaining with five buckets and
key % 5, place 6, 11, 16 and 7. What is the load factor? - A min-heap starts
[2, 9, 4]. Is it invalid because 9 appears before 4?
Answers: (1) The inserted heap is [3, 7, 25, 12]; removal returns 3 and leaves [7, 12, 25]. (2) Four slots: 3, 4, 5 and empty 6. (3) Bucket 1 has 6, 11 and 16; bucket 2 has 7. Alpha is 4/5 = 0.8. (4) It is valid: 2 is no larger than either child, and siblings need not be ordered.
Common mistakes and a short revision check
- Confusing a heap with a BST or a sorted array.
- Forgetting the last-node replacement during root removal.
- Choosing the larger child when sifting down a min-heap.
- Assuming equal priorities automatically preserve arrival order.
- Treating collisions as equal keys or overwriting another key.
- Claiming hash lookup is always O(1), without distribution and load assumptions.
- Erasing an open-addressing slot without preserving its search chain.
Before moving on, explain why a heap root is the minimum, why bottom-up heapify is linear, and why a collision still needs a key comparison. Trace one example on paper before running it.
More study help and sources
Return to Exam Notes, try the tested C Data Structures lab, or copy the Python examples into the Online Compiler. Code is not automatically prefilled.
Source notes: Python heapq documentation for heap invariants and priority-queue tie handling; OpenDSA binary heaps for bottom-up construction; Open Data Structures hashing for chaining, probing and expected-time assumptions; OpenDSA hash-table analysis for load factor. Explanations, code and exercises on this page are original. Earlier examples were checked with 500 seeded heap sequences and 200 seeded hash-map sequences, including duplicates, negative keys and missing-key errors.
Previous: Episode 6 | Next: Episode 8: graphs | Series index
Comments
Post a Comment