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

01. IPO

Optimal Target: O(n log n) time · O(n) space

Given an integer k representing the maximum number of distinct projects you can select, an integer capital representing your initial capital, an integer array profits where profits[i] is the net profit earned upon completing project i, and an integer array needs where needs[i] is the minimum capital required to start project i, return the maximum final capital achievable after finishing at most k projects. Starting a project does not deduct from your current capital; completing project i permanently adds profits[i] to capital.

EXAMPLE 1
Input: k = 2, capital = 0, profits = [1, 2, 3, 5], needs = [0, 1, 1, 4]
Output: 4
Explanation: With initial capital 0, only project 0 (needs[0] = 0, profits[0] = 1) is unlocked, raising capital to 1. Projects 1 and 2 (needs = 1, profits = 2 and 3) then unlock; selecting project 2 adds 3 for a final capital of 4.
VISUAL INPUT
min-heap by capital · capital→profit
0→11→21→34→5
AUTOMATED TEST SUITE
Test Case 1
Input: 2, 0, [1, 2, 3, 5], [0, 1, 1, 4]
Expected: 4
Test Case 2
Input: 3, 0, [1, 2, 3], [0, 1, 2]
Expected: 6
Test Case 3
Input: 2, 0, [5], [1]
Expected: 0
Pattern Trigger Hint ("How to Spot It")

options unlock over time, take the best → 2 heaps

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute max_capital against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

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