Heaps & Priority Queues

The running minimum that can't survive a deletion

In the foundation lesson, one variable (cheapest) tracked the minimum of a growing list of prices. That worked because prices only ever arrived. Now change one rule: after you read the minimum, you remove it. What is the new minimum? cheapest can't tell you. It kept the winner and threw away the runner-up.

Here is that workload at full size. A collection holds 100,000 numbers. 100,000 times, you remove the smallest one and add a new number.

• Rescan for the minimum every time: 100,000 × 100,000 = 10¹⁰ comparisons.
• Keep the list sorted, smallest at the end: removing is O(1), but each insert shifts about half the list. That's 50,000 moves × 100,000 inserts = 5 × 10⁹ moves.
• A heap: each removal and each insert walks one path of a tree with 17 levels. That's roughly 2 × 17 × 100,000 = 3.4 million steps.

The big idea: don't sort everything. Keep just enough order to know the winner, and make that order cheap to repair. A heap promises only that every parent is no larger than its children. That is enough to put the minimum on top, and after any change it can be repaired along a single path in O(log n).

Before you start. This lesson builds on Foundation: Arrays & Strings (running summaries, invariants, output contracts) and uses collections.Counter from Hash Maps & Sets. Tree vocabulary (root, parent, child, leaf, height) belongs to Trees & Advanced Structures; the few terms needed here are defined as they come up.

The contract: priority queue vs heap

A priority queue is a contract with three operations: insert an item, remove the item with the best priority, and peek at it. It says nothing about how. A binary heap is the usual way to keep that contract, and it is what Python's heapq implements. (Other heap designs exist, such as binomial and pairing heaps; "heap" in this lesson always means binary heap.)

The heap gives up fast search on purpose. When a problem needs "is x in here?" as well, pair the heap with a set or a dictionary. When it needs to delete arbitrary items, see lazy deletion in Pattern 6.

Part 1: The shape and the rule

A binary min-heap is a binary tree that obeys two rules:

1. Shape. Every level is full except possibly the last, and the last level fills from the left. This is a complete binary tree.
2. Order. Every parent is ≤ each of its children.

Follow any path downward and the values never decrease, so the root is the minimum. That is all the order there is. Siblings can be in either order. The second-smallest value is one of the root's two children, but nothing says which one. A max-heap flips the rule: every parent is ≥ its children.

A tree stored in a plain list

The shape rule means the tree has no gaps, so it fits in a list read level by level, left to right:

index:   0  1  2  3  4  5
value: [ 1, 3, 2, 7, 5, 9 ]

            1              level 0: index 0
          /   \
         3     2           level 1: indices 1, 2
        / \   /
       7   5 9             level 2: indices 3, 4, 5

For the node at index i (0-based):

• left child: 2 * i + 1
• right child: 2 * i + 2
• parent: (i - 1) // 2

Check one: the 9 sits at index 5, and its parent is (5 - 1) // 2 = 2, the value 2. The 9 is the left child of 2, because the last level fills from the left. No pointers and no node objects are needed: the arithmetic is the tree.

A complete tree with n nodes has height ⌊log₂ n⌋. For n = 100,000 that is 16, so every root-to-leaf path has at most 17 nodes. Every push and every pop walks at most one such path.

Predict first: which of these lists are valid min-heaps? [1, 5, 3, 9, 7], [2, 3, 1], [1, 2, 3, 4, 5, 6, 7], [3, 8, 4, 9, 1]. Then decide: is every sorted list a heap? Is every heap sorted?

Part 2: Two repairs, sift up and sift down

Every change to a heap breaks at most one spot, and one of two repairs fixes it. Both walk a single path, so both cost O(log n).

Push: append, then climb

Appending keeps the shape (the new item fills the next slot on the last level). It may break the order: the new item could be smaller than its parent. So swap it upward until its parent is no larger.

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break                          # order restored
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

def push(heap, x):
    heap.append(x)                         # keep the shape complete
    sift_up(heap, len(heap) - 1)           # then repair the order

Push 4 into [3, 5, 8, 9, 6, 12, 15]. It lands at index 7:

Pop: fill the hole from the bottom, then sink

Removing the root leaves a hole at the top. Moving any interior node up to fill it would open another hole, so instead take the last leaf, the one item whose removal keeps the shape complete, and put it at the root. It is probably too big for that spot, so swap it downward, always with its smaller child, until no child is smaller.

def sift_down(heap, i):
    n = len(heap)
    while True:
        smallest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            return                         # no child is smaller: done
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def pop(heap):
    last = heap.pop()                      # IndexError if empty, like heapq
    if not heap:
        return last
    top = heap[0]
    heap[0] = last                         # last leaf fills the hole at the root
    sift_down(heap, 0)
    return top

Pop from [3, 4, 8, 5, 6, 12, 15, 9]. The 3 leaves, and the last leaf, 9, moves to the root: [9, 4, 8, 5, 6, 12, 15].

pop returns 3, and [4, 5, 8, 9, 6, 12, 15] is a valid heap again, with the 4 you pushed now on top.

Why these repairs are enough

Sift up. Invariant: the list is a valid heap except that the moving item may be smaller than its parent. When the item and its parent swap, the parent moves down into a spot whose subtree was already all ≥ that parent, because the heap was valid before. So the only edge that can still be wrong is the one above the item's new position. Each swap moves that edge one level up. At the root, or at a parent that is no larger, the heap is whole.

Sift down. Invariant: the list is a valid heap except that the moving item may be larger than its children. Why the smaller child? After the swap, that child becomes the parent of its old sibling, so it must be ≤ that sibling, and only the smaller of the two qualifies. Each swap pushes the problem one level down, and at a leaf there is nothing left to break.

Each repair performs at most one swap per level: O(log n) time, O(1) extra space.

Traps

• Swapping with the first child that is smaller instead of the smaller child. It looks fine on small tests and silently corrupts the heap. The next exercise catches it.
• Assuming a right child exists. The last internal node can have a left child and no right child. Both left < n and right < n checks are needed.
• Dropping i > 0 in sift_up. In Python, (0 - 1) // 2 is -1, because // rounds toward minus infinity. Without the guard, the root gets compared with heap[-1], the last element, and may swap with it. No error is raised; the heap is just wrong. (In Java or C++, integer division truncates, so the parent of 0 comes out as 0 and the same slip happens to be harmless.)
• Popping an empty heap. pop([]) raises IndexError, just as heapq.heappop([]) does. Check if heap: first.

Your turn: pop twice from [1, 3, 2, 5, 6, 4] by hand using the correct rule. Then pop twice again from the original list with a buggy sift_down that swaps with the left child whenever the left child is smaller than the item, and only looks at the right child otherwise. What does each version return on the second pop?

Part 3: Building a heap in O(n)

You have all n items up front. The obvious build pushes them one at a time: n pushes at O(log n) each is O(n log n). On a descending input every new item is the smallest so far and climbs all the way to the root, so that bound is really paid.

There is a faster way. Sift down every internal node, from the last one back to the root. Leaves, which are indices n // 2 through n - 1, are already one-item heaps. Once both subtrees of a node are heaps, one sift_down from that node makes its whole subtree a heap. Going backwards guarantees both subtrees are finished first.

def heapify(a):
    for i in range(len(a) // 2 - 1, -1, -1):   # last internal node, back to the root
        sift_down(a, i)

Heapify [9, 5, 6, 2, 3]. With n = 5, the last internal node is index 5 // 2 - 1 = 1:

heapq.heapify produces the same [2, 3, 6, 5, 9] here.

Why it's linear

A sift-down costs at most the node's height, meaning how far it can sink. About half the nodes are leaves, with height 0. About a quarter have height 1, an eighth height 2, and so on. The total is about n/4 × 1 + n/8 × 2 + n/16 × 3 + …, and that series adds up to at most n. For n = 1,000,000 the heights add up to 999,993.

Pushing one at a time pays by depth instead: how far each item can climb. Most nodes sit near the bottom, so most depths are large. Same tree, opposite bill. Counting swaps on a descending input of 1,000,000 values:

So when all the items are available at the start, use heapq.heapify(items): O(n) time, in place, no extra list. Copy first (h = list(items)) if the caller's list must not change.

Your turn: heapify [5, 4, 3, 2, 1] by hand. Which index do you start at, how many swaps happen, and what list do you end with?

Part 4: Python's heapq on one screen

heapq is a set of functions that keep a plain list in min-heap order. There is no heap class; you pass the list in.

The two combined calls differ exactly when x is smaller than the root. heapreplace([5, 7, 9], 1) returns 5 and leaves [1, 7, 9]: the root goes no matter what. heappushpop([5, 7, 9], 1) returns 1 and leaves [5, 7, 9], because the new item was the smallest. Each does at most one sift instead of the two that a pop plus a push would do.

⚠️ Only h[0] has a guaranteed meaning. h[1] is not necessarily the second smallest, and looping over h does not visit items in sorted order.

Max-heaps: negate

For numbers, push -x and negate what comes out: -heapq.heappop(h), -h[0]. Python integers never overflow, so negation is always safe. Python 3.14 added heappush_max, heappop_max, heapify_max, heapreplace_max and heappushpop_max. Judges and interview machines may run an older Python where these don't exist, so negation remains the portable habit. For keys you can't negate, such as strings, see the plot twist in Pattern 2.

Tuples, ties and tie-breakers

heapq compares whole items with <, and tuples compare field by field. So (priority, item) orders by priority, and a tie falls through to the next field.

Predict first: what does this print?

import heapq

h = []
for name, pr in [("write", 2), ("deploy", 1), ("build", 2)]:
    heapq.heappush(h, (pr, name))
print([heapq.heappop(h)[1] for _ in range(3)])

Ties cause two different kinds of bug:

• The next field can't be compared. Make the payload a dict, a ListNode or any object without __lt__, and the tie raises TypeError: '<' not supported between instances of 'dict' and 'dict'. It only fires when two tied entries actually meet. In the example above, all three pushes succeed and the crash comes on a pop, so a small test with distinct priorities never sees it.
• The next field can be compared, but shouldn't decide. Strings, lists and tuples compare fine (lists compare element by element), so ties are settled silently by the payload, as in the prediction.

The fix for both is a unique counter in the middle:

import heapq, itertools

counter = itertools.count()
h = []
for name, pr in [("write", 2), ("deploy", 1), ("build", 2)]:
    heapq.heappush(h, (pr, next(counter), name))
print([heapq.heappop(h)[2] for _ in range(3)])   # ['deploy', 'write', 'build']

The counter never ties, so the payload is never compared, and equal priorities come out first in, first out. Any value that is unique among the live entries works: the patterns below use a list index.

Pattern 1: The bouncer (top k, kth largest)

Smell: "the k largest", "the kth largest", "the k closest", especially when k is much smaller than n or the values arrive as a stream.

Here's the task: return the kth largest value in nums, counting duplicates. This is LeetCode 215: Kth Largest Element in an Array.

Predict first: you are keeping the 3 largest values seen so far, and a new value arrives. Which kept value do you compare it with, the largest or the smallest? So which kind of heap do you need?

The whole-array versions. sorted(nums)[-k] is O(n log n) time and O(n) space. A max-heap of everything (negate, heapify, pop k times) is O(n + k log n) time and O(n) space. That second one is not slower than what follows; its cost is memory, because it copies all n values.

The bouncer. Keep at most k values in a min-heap. The root is the weakest member, and a newcomer replaces it only if it is larger.

import heapq

def find_kth_largest(nums, k):
    heap = []                              # the k largest values seen so far
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:                  # x beats the weakest member
            heapq.heapreplace(heap, x)     # evict the weakest, admit x
    return heap[0]                         # weakest of the top k = kth largest

Trace nums = [3, 2, 1, 5, 6, 4], k = 3:

It returns 4. The three largest values are 6, 5 and 4.

Why it works. Invariant: after each value, the heap holds the k largest values seen so far (duplicates counted), so heap[0] is the kth largest so far. If x ≤ heap[0], there are already k seen values at least as large as x, so admitting x can't change the kth largest. If x > heap[0], the old root drops to rank k + 1 and has to leave.

Cost. Each of the n values costs at most O(log k): O(n log k) time, O(k) extra space.

Is this the fastest way? Not always. On paper, O(n + k log n) for heapify-then-pop is never worse than O(n log k). Quickselect (partition as in quicksort, then recurse into one side only) runs in expected O(n). The bouncer's real advantages are memory, since it never holds more than k values, and streams, since it has an answer ready after every value. That makes it the natural fit for LeetCode 703: Kth Largest Element in a Stream, which is the same heap kept inside a class.

Edge cases and traps:

• Duplicates count separately: [3, 2, 3, 1, 2, 4, 5, 5, 6] with k = 4 gives 4 (the top four are 6, 5, 5, 4).
• k = n returns the minimum; k = 1 returns the maximum.
• > or >= in the guard both work, because replacing a value with an equal one leaves the same values. > just skips useless work.
• Calling heapreplace without the guard is a bug: it evicts the weakest member even when x is smaller. heapq.heappushpop(heap, x) needs no guard, since it hands back the smaller of x and the root.

Your turn: return the k points closest to the origin, in any order. This is LeetCode 973: K Closest Points to Origin. Use O(k) extra space. Predict the answer for [[3, 3], [5, -1], [-2, 4]] with k = 2, then write it. Who is the bouncer this time?

import heapq

def k_closest(points, k):
    heap = []                              # max-heap by distance: store -d
    for x, y in points:
        d = x * x + y * y
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif d < -heap[0][0]:              # closer than the farthest kept point
            heapq.heapreplace(heap, (-d, x, y))
    return [[x, y] for _, x, y in heap]

Pattern 2: Count first, then pick

Smell: "the k most frequent", or more generally the top k by a score you have to compute first.

The task is LeetCode 347: Top K Frequent Elements. For nums = [1, 1, 1, 2, 2, 3] and k = 2, the answer is [1, 2] in any order. The problem promises the answer is unique.

Two steps. First count, which is expected O(n) with a Counter. Then run the bouncer from Pattern 1 on the counts:

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)                 # value -> count
    heap = []                              # (count, value), least frequent on top
    for value, c in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (c, value))
        elif c > heap[0][0]:
            heapq.heapreplace(heap, (c, value))
    return [value for _, value in heap]

With m distinct values, this is O(n + m log k) time and O(m) extra space. Tied counts fall through to the values, which are integers, so the tuples always compare. The library one-liner does the same selection: heapq.nlargest(k, counts, key=counts.get).

The problem's follow-up asks for better than O(n log n). The heap delivers that only when k is small: with many distinct values and a k such as √n, O(n + m log k) still grows like n log n. The guaranteed way avoids the heap entirely: a count is between 1 and n, so values can be dropped into buckets indexed by count and read back from the top. That takes O(n) time.

from collections import Counter

def top_k_frequent_buckets(nums, k):
    counts = Counter(nums)
    by_count = [[] for _ in range(len(nums) + 1)]   # by_count[c] = values seen c times
    for value, c in counts.items():
        by_count[c].append(value)
    result = []
    for c in range(len(nums), 0, -1):               # most frequent first
        for value in by_count[c]:
            result.append(value)
            if len(result) == k:
                return result
    return result

Plot twist: when the tie-break can't be negated

LeetCode 692: Top K Frequent Words returns the k most frequent words, sorted by count from high to low, with ties in alphabetical order. Try the bouncer on (count, word) with words = ["c", "b", "a"] and k = 2. Every count is 1, so the guard c > heap[0][0] never admits "a". The result is ["b", "c"], but the right answer is ["a", "b"].

The bouncer has to evict the weakest word. Here that means the lowest count and, among equal counts, the alphabetically last word. A min-heap on (count, word) has the alphabetically first word on top, which is the wrong direction for the second field. For numbers you would negate, but you can't negate a string.

The clean way out is to flip the whole question. The answer is the k smallest words under the key (-count, word):

import heapq
from collections import Counter

def top_k_frequent_words(words, k):
    counts = Counter(words)
    return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))

nsmallest keeps a size-k heap internally and returns its results already sorted, so this runs in O(n + m log k) time. The alternative is a small wrapper class whose __lt__ compares counts normally and words in reverse. It works, but it is more code to get right.

Pattern 3: One head per list (k-way merge)

Smell: k inputs that are each sorted, and you need them combined in order, or you need the kth smallest across all of them.

The task is LeetCode 23: Merge k Sorted Lists: merge k sorted linked lists into one sorted linked list.

Predict first: you have three sorted lists. Before you take anything, which items could possibly be the overall smallest? After you take one, which could be next?

The slow versions. Dumping every value into one list and sorting it takes O(N log N) time and O(N) space, where N is the total number of nodes. Merging the lists one at a time into a growing result re-walks that result on every merge. With 10,000 one-node lists, that walks 1 + 2 + … + 9,999 = 49,995,000 nodes.

The fast version. Keep the candidates, one head per list, in a min-heap:

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)                    # one entry per non-empty list
    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap) # smallest head overall
        tail.next = node
        tail = node
        if node.next:                      # list i supplies its next head
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Trace the problem's example, lists [1, 4, 5], [1, 3, 4] and [2, 6] (numbered 0, 1 and 2). The heap starts as (1, list 0), (1, list 1), (2, list 2). Heap contents are shown sorted for reading; the real list is only heap-ordered.

Why the i? ListNode defines no <. The first two entries tie on value 1, so Python moves on to the second field. Build the heap from (node.val, node) and heapify fails immediately on this very example with TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'. With i in the middle, a tie compares list numbers instead. The heap holds at most one entry per list, so no two entries ever share an i, and the nodes are never compared.

Why it works. Invariant: the heap holds exactly the current head of every list that still has nodes. Each head is the smallest remaining item of its own list, so the smallest head is the smallest remaining item overall. Popping it and pushing its successor restores the invariant.

Cost. N pops and at most N pushes on a heap of size at most k: O(N log k) time, O(k) extra space. The nodes are relinked, not copied. For the 10,000 one-node lists above, that's about 10,000 × log₂ 10,000 ≈ 133,000 steps instead of 50 million.

Two alternatives are worth knowing. Merging the lists in pairs (1 with 2, 3 with 4, …, then the results in pairs) is also O(N log k). For Python iterables, heapq.merge(*iterables) does this k-way merge lazily for you.

Your turn: in an n × n matrix, every row and every column is sorted in ascending order. Return the kth smallest value. This is LeetCode 378: Kth Smallest Element in a Sorted Matrix. Predict the answer for [[1, 5, 9], [10, 11, 13], [12, 13, 15]] with k = 8, then write a heap solution. How many rows ever need to be in the heap?

import heapq

def kth_smallest(matrix, k):
    n = len(matrix)
    heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]   # head of each row
    heapq.heapify(heap)
    for _ in range(k - 1):                 # discard the k - 1 smallest
        val, r, c = heapq.heappop(heap)
        if c + 1 < n:
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
    return heap[0][0]

Pattern 4: Two heaps that meet in the middle

Smell: "the median", "the middle", "split into two balanced halves", on a collection that keeps changing.

The task is LeetCode 295: Find Median from Data Stream. Support addNum(num) and findMedian(). With an even count, the median is the mean of the two middle values.

A sorted list makes findMedian O(1), but each addNum has to insert in the middle and shift, which is O(n). One heap only knows one end. So use two heaps whose tops face each other:

    low: a max-heap                  high: a min-heap
    [1, 3, 5]  -> top 5      |      top 8 <-  [8, 15]

    rule 1: everything in low <= everything in high
    rule 2: len(low) == len(high)  or  len(low) == len(high) + 1

The median sits right at the boundary. With an odd count it is the top of low. With an even count it is the mean of the two tops.

Predict first: you add the numbers 1 to 6 in some scrambled order. Which numbers end up in low? Does the order of insertion matter?

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []    # smaller half as a max-heap: values stored negated
        self.high = []   # larger half as a min-heap

    def addNum(self, num):
        heapq.heappush(self.low, -num)                        # 1. join the low half
        heapq.heappush(self.high, -heapq.heappop(self.low))   # 2. low's largest moves up
        if len(self.high) > len(self.low):                    # 3. low keeps the extra item
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Trace the stream 5, 15, 1, 3, 8. The table shows real values; the low list actually stores them negated, ending as [-5, -1, -3].

Why the three steps keep both rules.

• Rule 1. Step 1 puts num into low, and step 2 immediately sends the largest item of low ∪ {num} to high. Whatever stays in low is ≤ that item. It is also ≤ everything already in high: either the item that moved was num itself, and the old low was already fine, or num stayed behind while the old maximum of low moved up, and num is ≤ that old maximum. Step 3 moves the smallest item of high down, which keeps the rule too.
• Rule 2. If the sizes were equal, step 2 leaves high one larger and step 3 moves one item back, so low ends one larger. If low had the extra item, step 2 evens the sizes and step 3 does nothing.

Cost. At most three pushes and two pops per add: O(log n) for addNum and O(1) for findMedian. The space is O(n). Every value is stored somewhere, so the two heaps do not save memory; they save time.

Details that bite:

• Read low's top as -self.low[0]. Forgetting that minus sign is a common bug.
• Either heap may hold the extra item, as long as findMedian agrees. This version gives it to low.
• In Python, (a + b) / 2 can't overflow. In Java or C++, two ints near 2³¹ overflow when added, so compute the sum in long, or use a / 2.0 + b / 2.0.
• The same split works for any fixed percentile. For the 90th, keep about 90% of the items in low: 9 in low for every 1 in high. For the 25th percentile, the ratio is 1 to 3. The space is still O(n).

Your turn: a teammate "simplifies" addNum so that each number goes straight into whichever heap is smaller:

    def addNum(self, num):
        if len(self.low) <= len(self.high):   # push to whichever half is smaller
            heapq.heappush(self.low, -num)
        else:
            heapq.heappush(self.high, num)

findMedian is unchanged. Find a stream of three numbers that makes it return a wrong median. Which rule does the shortcut break?

Pattern 5: Sort by time, heap the candidates

Smell: intervals, start and end times, tasks that become available at some moment. The questions are "how many resources?" or "at each moment, which available item is best?"

Sort the events by time, then keep in a heap the candidates for the next decision. For Meeting Rooms, the candidates are rooms keyed by when each one frees up, idle rooms included. For the unlock pool below, they are the items already unlocked.

Meeting Rooms II

Given meeting intervals [start, end), find the minimum number of rooms. This is LeetCode 253: Meeting Rooms II, a premium problem. A meeting that ends at 10 frees its room for one that starts at 10.

Process meetings in order of start time. Keep a min-heap with one entry per room opened so far: the time that room is next free. For each meeting, check the room that frees up earliest. If it is already free, reuse it; otherwise every room is busy, so open a new one.

import heapq

def min_meeting_rooms(intervals):
    ends = []                              # when each open room frees up; earliest on top
    for start, end in sorted(intervals):   # meetings in order of start time
        if ends and ends[0] <= start:      # the earliest-free room is already free
            heapq.heapreplace(ends, end)   # reuse it
        else:
            heapq.heappush(ends, end)      # every room is busy: open one
    return len(ends)

Trace [[0, 30], [5, 10], [15, 20]]:

It returns 2.

⚠️ The heap is not "the meetings in progress". Trace [[0, 10], [1, 2], [3, 4], [11, 12]]:

At time 11 only one meeting is running, yet the heap has two entries. The room that freed at 10 is still in the heap, because the loop reuses at most one room per meeting. The heap never shrinks. Its size is the number of rooms opened, and that equals the peak overlap.

Why it's the minimum. A new room is opened only when even the earliest-free room is still busy at start. At that moment every open room holds a meeting that overlaps start, so r rooms means r meetings running at once, and no schedule can use fewer than r rooms. The algorithm never opens more than it needs, so it meets that bound exactly.

Traps:

• Boundaries. <= treats [5, 10] and [10, 15] as compatible, so [[1, 5], [5, 10], [10, 15]] needs 1 room. If a problem's intervals include both endpoints, use <.
• Forgetting to sort. On [[5, 10], [0, 3]] the unsorted loop opens two rooms, because it checks the 10 against a meeting that starts at 0. The answer is 1.

Cost. O(n log n) time for the sort and heap operations; O(n) extra space. A heap-free alternative sorts the start times and end times separately and sweeps them with two pointers, in the same O(n log n).

The unlock pool

A second shape of the same idea: items unlock as a threshold rises, and once unlocked they stay available. Keep the items sorted by unlock threshold with a pointer into them. Every time the threshold rises, push the newly unlocked items into a heap ordered by what you want to pick next.

Your turn: you start with capital w and may finish at most k projects, one at a time. Project i needs capital[i] to start and adds profits[i] to your capital when done. Maximize your final capital. This is LeetCode 502: IPO. Predict the result for k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1], then write it for n and k up to 10⁵.

import heapq

def find_maximized_capital(k, w, profits, capital):
    projects = sorted(zip(capital, profits))   # cheapest to start first
    affordable = []                            # max-heap of profits (negated)
    i = 0
    for _ in range(k):
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(affordable, -projects[i][1])   # unlocked for good
            i += 1
        if not affordable:
            break                              # nothing we can start
        w -= heapq.heappop(affordable)         # take the best profit
    return w

Pattern 6: Lazy deletion

Smell: something must leave the heap, but it isn't on top. A price was corrected, a value slid out of a window, or a better distance was found for a node.

heapq has no "delete x". Finding x is O(n), because heap order doesn't help a search. Removing an item at a known index is O(log n): move the last item into its place, then sift it up or down. But you would have to track every item's index through every swap. The lazy alternative is simpler. Leave dead entries in the heap, and throw them away when they surface at the top. Only the top is ever read, so a dead entry buried below does no harm.

Stale entries: check against the truth

LeetCode 2034: Stock Price Fluctuation receives (timestamp, price) records out of order, and a later record for the same timestamp corrects the earlier price. It must answer current() (the price at the latest timestamp), maximum() and minimum().

Keep the truth in a dictionary and push every record into two heaps. When you read a top, compare it with the dictionary. If they disagree, that entry is stale: pop it and look again.

import heapq

class StockPrice:
    def __init__(self):
        self.price = {}            # timestamp -> latest price: the source of truth
        self.latest = 0
        self.max_heap = []         # (-price, timestamp); may hold stale entries
        self.min_heap = []         # (price, timestamp); may hold stale entries

    def update(self, timestamp, price):
        self.price[timestamp] = price
        self.latest = max(self.latest, timestamp)
        heapq.heappush(self.max_heap, (-price, timestamp))
        heapq.heappush(self.min_heap, (price, timestamp))

    def current(self):
        return self.price[self.latest]

    def maximum(self):
        while -self.max_heap[0][0] != self.price[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)          # stale: that price was corrected
        return -self.max_heap[0][0]

    def minimum(self):
        while self.min_heap[0][0] != self.price[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)
        return self.min_heap[0][0]

When update(1, 3) corrects timestamp 1, the old entry (-10, 1) stays in the heap. It only gets removed once it reaches the top and fails the check.

Dijkstra's shortest-path algorithm uses exactly this check: it skips a popped (distance, node) if a shorter distance to that node is already known. You'll meet it in Shortest Path Algorithms.

Deletion counts: when entries have no identity

Sometimes the heap holds bare values, and "delete one 7" has no timestamp to check against. Sliding windows are the typical case: the value leaving on the left must go. Then remember how many copies of each value are waiting to be deleted:

import heapq
from collections import Counter

class LazyMinHeap:
    def __init__(self):
        self.heap = []
        self.pending = Counter()   # value -> copies deleted but still in the list
        self.size = 0              # live items only

    def push(self, x):
        heapq.heappush(self.heap, x)
        self.size += 1

    def remove(self, x):           # caller guarantees one live copy of x exists
        self.pending[x] += 1
        self.size -= 1

    def _prune(self):
        while self.heap and self.pending[self.heap[0]]:
            self.pending[heapq.heappop(self.heap)] -= 1

    def top(self):
        self._prune()
        return self.heap[0]

    def pop(self):
        self._prune()
        self.size -= 1
        return heapq.heappop(self.heap)

Three details carry the correctness:

• A Counter, not a set. Push 7, 7 and 9, then remove 7 twice. A set remembers "7 is deleted" only once, so after one 7 is pruned the other 7 surfaces as a live item and top() returns 7. With counts, both copies are skipped and top() returns 9.
• A separate live size, and separate books per heap. len(self.heap) counts dead entries too, so anything that balances heaps by size, such as two heaps in a sliding-window median, has to use the live count. With two heaps, give each its own pending counts: a value can have copies in both halves, and a shared counter may skip the copy in the wrong heap.
• Only remove what is present. Marking an absent value makes a later genuine push of that value vanish.

Cost. Each entry is pushed once and popped at most once. One call may pop many dead entries, but across q operations the total is O(q log q). This is an amortized bound: expensive calls are paid for by the cheap pushes that created the dead entries. Memory is the price: dead entries stay until they surface, so the list can hold every entry ever pushed. If that matters, rebuild the heap from live items once dead ones outnumber them.

Final round: no label on the problem

Real problems don't announce "use a heap". For each one, decide what goes in the heap, which kind of heap, and when things leave it.

Challenge 1: Last Stone Weight

Each turn, smash the two heaviest stones together. Equal stones both vanish. Otherwise the lighter one vanishes and the heavier one loses the lighter one's weight. Return the last stone's weight, or 0 if none is left. [2, 7, 4, 1, 8, 1] gives 1. This is LeetCode 1046: Last Stone Weight.

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]            # max-heap via negation
    heapq.heapify(heap)
    while len(heap) > 1:
        y = -heapq.heappop(heap)           # heaviest
        x = -heapq.heappop(heap)           # second heaviest
        if y > x:
            heapq.heappush(heap, -(y - x))
    return -heap[0] if heap else 0

Challenge 2: Reorganize String

Rearrange the letters of s so that no two adjacent letters are equal, or return "" if that's impossible. "aab" gives "aba", and "aaab" gives "". This is LeetCode 767: Reorganize String. Which letter should you place next, and what stops you from placing the same letter twice in a row?

import heapq
from collections import Counter

def reorganize_string(s):
    heap = [(-c, ch) for ch, c in Counter(s).items()]
    heapq.heapify(heap)
    out = []
    held = None                            # the char just used sits out one turn
    while heap:
        neg, ch = heapq.heappop(heap)      # most remaining copies, not held
        out.append(ch)
        if held:
            heapq.heappush(heap, held)     # previous char may compete again
        held = (neg + 1, ch) if neg + 1 < 0 else None
    return "".join(out) if held is None else ""

Challenge 3: Sliding Window Maximum

Return the maximum of every window of size k. [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 gives [3, 3, 5, 5, 6, 7]. This is LeetCode 239: Sliding Window Maximum, with n up to 10⁵.

import heapq

def max_sliding_window(nums, k):
    heap = []                              # (-value, index)
    result = []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        if i >= k - 1:
            while heap[0][1] <= i - k:     # top has left the window: stale
                heapq.heappop(heap)
            result.append(-heap[0][0])
    return result

Cheat sheet

Before moving on, close this page and explain, from a blank editor, one heap problem from this lesson. Cover what each heap entry means and when it leaves, why the top is the right thing to read at every moment (the invariant), what happens on a tie, and what the cost is in terms of n and k. Then name one change to the problem that would make a heap the wrong tool, such as a static array with many queries, or a need to search by value.

Next: Shortest Path Algorithms puts this heap to work in Dijkstra's algorithm, stale entries included. Trees & Advanced Structures covers balanced search trees and segment trees, for when you need search, deletion by value, or range queries that a heap can't answer.