CODING PATTERNS · LESSON 6 OF 28 · 39 MIN VIDEO · 12 PROBLEMS

Heaps

Module Progress (0 / 12 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (39 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

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).

WHEN TO USE THIS PATTERN
  • 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.
COMMON INTERVIEW PITFALLS
  • 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.
Min-Heap of Resource End Times (Interval Scheduling)Finding minimum concurrent resources or reusing earliest-finishing machines across start-sorted intervals.
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)
Two-Heap Partition (Running Median)Maintaining O(1) median queries over a dynamic stream by balancing a lower max-heap (negated) and an upper min-heap.
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))
Lazy Deletion with On-Demand Root PruningRemoving arbitrary out-of-window elements from heaps in amortized O(log n) time without O(n) interior scans.
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
🔒 PRO PROBLEMTarget: O(n log n) time · O(n) space

03. Sliding Window Median

Pattern Trigger: median of a sliding window → 2 heaps + lazy deletion

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

In a min heap, where can you always find the largest value?