Heaps — How the Pattern Works
A binary heap implements a priority queue inside a complete binary tree stored contiguously in an array, maintaining the heap-order invariant that every parent at index i is less than or equal to its children at 2i + 1 and 2i + 2 in a min-heap (or greater than or equal to in a max-heap). This structure guarantees O(1) access to the current extremum at index 0 and O(log n) insertions and removals via sift-up and sift-down passes. By dynamically maintaining priority order across state mutations—or pairing complementary heaps to track order statistics, thresholds, and multi-rule resource states—heaps replace repeated O(n) linear scans and O(n log n) re-sorts with O(log n) updates, reducing overall runtime from O(n^2) or O(n^2 log n) to O(n log n).
- Repeatedly querying and extracting the minimum or maximum element from a dynamic set whose contents or priorities mutate after every step (Huffman-style merges, diminishing-return marginal gains, or backward state reduction).
- Maintaining the running median or balanced quantile split of an online data stream or fixed-width sliding window.
- Assigning sorted time intervals to reusable resources (machines, meeting rooms, numbered chairs) governed by earliest completion time and/or lowest resource ID.
- Selecting optimal greedy actions from a candidate pool where monotonic progress (such as growing capital) progressively unlocks previously ineligible options.
- Permuting or constructing sequences subject to group-preservation or consecutive-run constraints by greedily drawing the highest-priority valid element.
- Forgetting that Python's heapq module implements only a min-heap: simulating a max-heap requires negating numeric priorities on both insertion (-x) and extraction (-heappop(heap)), while keeping secondary tie-breaker fields oriented in the desired order.
- Relying on len(heap) when lazy deletion is active: logically deleted elements remain buried inside the heap array until they reach index 0, so partition balance must track explicit live-element counters and prune stale roots immediately before inspecting heap[0].
- Omitting deterministic tie-breakers on composite heap tuples: in multi-resource problems such as Meeting Rooms III, pushing (end_time, room_id) ensures equal completion times automatically break ties toward the lowest room_id without comparing non-orderable objects.
- Releasing and acquiring resources in the wrong order at boundary timestamps: when leave_time == arrive_time frees a resource immediately, always pop all entries satisfying end <= start before allocating a resource for the current event.
from heapq import heappush, heappop
def min_resources(intervals):
intervals.sort()
active_ends = []
for start, end in intervals:
if active_ends and active_ends[0] <= start:
heappop(active_ends)
heappush(active_ends, end)
return len(active_ends)from heapq import heappush, heappop
def insert_and_balance(small, large, x):
if not small or x <= -small[0]:
heappush(small, -x)
else:
heappush(large, x)
if len(small) > len(large) + 1:
heappush(large, -heappop(small))
elif len(large) > len(small):
heappush(small, -heappop(large))from heapq import heappop
def mark_deleted(dead, val):
dead[val] = dead.get(val, 0) + 1
def prune_stale_roots(heap, dead, sign=1):
while heap and dead.get(sign * heap[0], 0) > 0:
dead[sign * heappop(heap)] -= 1