Heap (Priority Queue)

Start with a small example: the values 3, 1, 5 arrive in that order, and you want to keep the largest two. After 3 and 1, both slots are full. When 5 arrives, one has to go, and the one that goes is the smaller of the two, 1. So a newcomer only needs to be compared with "the worst of what is kept right now", and that is what belongs on top of the heap.

For any heap problem, first decide what the heap holds and who is on top, then decide what to sort by.

Every version keeps three rules:

1. First write down, in one sentence, what the heap holds and who is on top. Min-heap or max-heap is decided by "who should be on top", not by whether the problem asks for large or small. For example, the heap for "the k largest" has the smallest of those k on top, so it's a min-heap.
2. The heap only holds candidates that are eligible right now. Put things in as late as possible: in a k-way merge each list contributes only its head; in a search over an implicit graph you only push the successors of what was just popped; in scheduling problems a candidate goes in only once its time has come or the money is there.
3. Pop order is best-to-worst order. The i-th pop is the i-th smallest (or i-th best). To get the k-th, pop k times.

The article goes in this order, and each step adds exactly one idea:

When to Use This Pattern

The brute force rescans every time it needs the extreme value. Take LC 1046: each round, smash the two heaviest stones together and put the leftover back, until one stone is left. With n stones that's about n rounds, and the three approaches cost:

Why is a heap fast at both ends? It only guarantees one thing: every node is no larger than its children (for a min-heap). A heap is a complete binary tree stored in an array: index i has children 2i + 1 and 2i + 2 and parent (i - 1) // 2. A pushed element starts at the end and swaps upward, at most the tree height, O(log n) times; popping the top moves the last element to the top and swaps it down, also O(log n). Nobody cares which sibling is larger, and that is the sorting work saved.

It also means heap[1] is not necessarily the second smallest. After heapq.heapify([1, 5, 2]) the array is still [1, 5, 2], and the second smallest, 2, is at heap[2].

Recognition Checklist

• You repeatedly take the min or max from a set that keeps changing
• There is a k: k-th largest, top k, k closest
• You merge several sorted sequences in order, or "emit them one by one from smallest up"
• Data arrives one at a time and each time you must report the current extreme or median
• You greedily pick the current best at every step, and candidates join or leave over time

Before You Code

Before writing code, answer these three:

1. What does the heap hold, and who is on top? Write it as one sentence, e.g. "the k points closest to the origin seen so far; the top is the farthest of them". If the top is "the largest", it's a max-heap (negate values in Python). To compare by several fields, store tuples with the priority first.
2. When does something enter the heap, and when does it leave? Gatekeeper heap: push directly while there are fewer than k; once full, a newcomer enters only if it beats the top, pushing the top out. Best-first: each pop pushes the popped item's successors. Scheduling: push once the condition holds, and pop the current best each time.
3. How large can the heap get? Do you need to dedup? How many rounds? These three numbers give the complexity. A gatekeeper heap never exceeds k; best-first pops 1 and pushes b per round, so over k rounds the heap holds at most 1 + k(b − 1).

The three answers connect: question 1 fixes who is on top, so question 2 can say what "beats the top" means; question 2 fixes how many go in and out per round, so question 3 can compute the size.

Try it on LC 973 K Closest Points to Origin.

The input is a list of 2D points points (each one [x, y]) and an integer k, with 1 ≤ k ≤ the number of points. Return the k points closest to the origin (0, 0) by Euclidean distance, in any order. You return the coordinates, not the distances and not the indices.

For example, [[1, 3], [-2, 2]] with k = 1 → [[-2, 2]]: the squared distance of (1, 3) is 1 + 9 = 10, and of (-2, 2) it is 4 + 4 = 8, so the second is closer.

• What it holds: the k closest points seen so far. The top is the farthest of these k, the first one to drop out. The top must be the farthest, so it's a max-heap. Python only has a min-heap (Step 1 covers this), so store (-dist², x, y): after negating, the farthest point is the most negative and sits on top of the min-heap. Comparing squared distances is enough: a larger square means a larger distance, so there's no square root.
• In and out: push directly while there are fewer than k. Once full, if a new point is closer than the top, it replaces the top; otherwise skip it.
• Size: never more than k. Each point costs at most one push and one pop, O(log k) each, O(n log k) in total. Each point is seen once, so no dedup.

Step 2 turns this into code. Before that, Step 1 covers how Python's heapq works.

Kth Largest Element in an Array (LeetCode 215)

Given an integer array and 1≤k≤length, return the kth largest value with duplicate positions counted separately. Two equal values may occupy first and second place; this is not the kth distinct value.

Input: nums = [3, 1, 5, 2, 4], k = 2. Expected: 4.

The heap holds the k largest values seen so far; it is a min-heap, so the top is the smallest of them, the gatekeeper. (The heap column is shown sorted for readability; the real list order inside heapq can differ.)

1. Walk it by hand

2. Read the rule off the table

• While the heap has fewer than k values, push every number.
• Once it is full, compare the newcomer with the gatekeeper heap[0]: only a larger value gets in, pushing the gatekeeper out; otherwise skip it.
• After the last number, the heap holds the k largest values and the gatekeeper is the k-th largest.

3. Turn each row into code

import heapq

def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]

Core Templates

All six steps and the advanced section use the same approach: answer the three questions first, then check against the three rules at the top: is the top really the one I wrote down, did anything enter the heap before it was eligible, and is the pop order the order I want.

Step 1: heapq is a min-heap; a max-heap stores negatives

Problem: repeatedly smash the two heaviest stones; equal weights both shatter, otherwise the difference goes back. Return the last remaining weight (LC 1046).

The input is a list of positive integers, the stone weights. Each round must take the two heaviest stones right now; call the heavier y and the lighter x. If y == x, both shatter. Otherwise x shatters and y becomes y − x and goes back. Keep going until at most one stone is left, and return its weight, or 0 if none is left.

For example, [2, 7, 4, 1, 8, 1] → 1 (the table below works through it round by round); [2, 2] → 0: the two stones weigh the same and both shatter.

The smashing order is fixed by the rules; you can't choose an order to make the result smaller.

The three questions:

• What it holds: every stone not yet shattered, heaviest on top. The largest must be on top, so it's a max-heap.
• In and out: pop two each round, and push one difference when the weights differ.
• Size: at least one stone fewer each round, at most n rounds at O(log n) each, O(n log n) in total.

Python's heapq is not a class; it's a set of functions that operate on a plain list:

It is only a min-heap: h[0] is always the minimum. For a max-heap, store negatives: negate on the way in and negate again on the way out. For example, weights 2, 7, 4 are stored as -2, -7, -4; the min-heap's top is -7, and negating it gives 7, the heaviest. Write the two negations together; miss one and the result flips.

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]     # min-heap only: store negatives for a max-heap
    heapq.heapify(heap)             # build the heap in place, O(n)
    while len(heap) > 1:
        y = -heapq.heappop(heap)    # heaviest, back to positive
        x = -heapq.heappop(heap)    # second heaviest, so y >= x
        if y != x:
            heapq.heappush(heap, -(y - x))  # y - x is positive; negate it before pushing
    return -heap[0] if heap else 0  # one stone left: back to positive; none left: 0


assert last_stone_weight([2, 7, 4, 1, 8, 1]) == 1
assert last_stone_weight([2, 2]) == 0       # the example from the statement
assert last_stone_weight([1]) == 1
assert last_stone_weight([3, 3]) == 0
assert last_stone_weight([]) == 0

stones = [2, 7, 4, 1, 8, 1]. The "Heap after" column is written largest first, using the original positive weights (the array inside heapq holds negatives, and not necessarily in this order):

One stone is left, with weight 1.

The heap is built with heapify because turning an existing list into a heap in place is O(n); n separate heappush calls are O(log n) each, O(n log n) in total.

Tuples as priorities. Many later problems order by "A first, then B". For those, push tuples (A, B, ...). Python compares two tuples by field 0 first; only on a tie does it compare field 1, then field 2, and so on. So if the priority is field 0, the heap is ordered by priority.

assert (1, "b") < (2, "a")      # field 0: 1 < 2 already decides it; the rest is never looked at
assert (1, "a") < (1, "b")      # field 0 ties, so field 1 decides: "a" < "b"
assert (-8, 2) < (-5, 9)        # with negatives, the originally larger value (8) comes first

The catch: whenever the leading fields tie, Python goes on to compare the next field. If that field is a dict, a ListNode, or anything else with no ordering, you get a TypeError. The fix is to insert a field in the middle that is always distinct and comparable, such as an index: (val, i, node). On equal val it compares i, i is always different, so node is never compared. Step 3 uses this.

Variation: push everything, pop k times

Practice here (original problem) ↗

The input is an integer array nums and k (0 ≤ k ≤ its length). Return the k smallest numbers in ascending order. Repeated values count separately.

For example, [3, 4, 1, 2, 5] with k = 3 → [1, 2, 3]; [5, 5, 1] with k = 2 → [1, 5]: the two 5s count separately, so the second smallest is 5.

Think first: Rule 3 says pop order is smallest first. If all the data is already in hand, what's the least effort way to do this? How long do building the heap and popping k times take? Will it modify the array the caller passed in?

import heapq

def k_smallest(nums, k):
    heap = nums[:]                  # the slice [:] makes a copy; the input stays unchanged
    heapq.heapify(heap)             # O(n)
    return [heapq.heappop(heap) for _ in range(k)]   # O(log n) each; _ is an unused loop variable


assert k_smallest([3, 4, 1, 2, 5], 3) == [1, 2, 3]
assert k_smallest([5, 5, 1], 2) == [1, 5]
assert k_smallest([7], 0) == []

Step 1 recap

• What it solves: repeatedly taking the max or min from a set that keeps changing, at O(log n) per operation.
• The key line: heap = [-s for s in stones]. heapq only has a min-heap; a max-heap stores negatives.
• What the variation changes: the main problem pops 2 and pushes 1 per round; the variation never pushes back, it just heapifys everything and pops k times.
• Easiest mistake: storing negatives and forgetting to negate again when popping or reading heap[0]. When you write the push line, write the pop line's minus sign at the same time.

Step 2: The gatekeeper, a heap of size k

Problem: the k-th largest number in an array (LC 215).

The input is an integer array nums and k, with 1 ≤ k ≤ its length. Sort all the numbers from largest to smallest (repeated values each take a position) and return the value in position k.

For example, [3, 2, 3, 1, 2, 4, 5, 5, 6] with k = 4 → 4: largest first it's 6, 5, 5, 4, …; the two 5s each take a position, so the 4th is 4.

It is not "the k-th distinct value" (that would be 3), and it is not an index.

The three questions:

• What it holds: the k largest numbers seen so far. The top is the smallest of these k; call it the gatekeeper: the worst member of the "top k" and the first to be pushed out. The top must be the smallest, so it's a min-heap.
• In and out: push directly while there are fewer than k. Once full, compare each newcomer with the gatekeeper: only if it's larger does it earn a place in the top k, replacing the gatekeeper; otherwise skip it.
• Size: at most k. Each number causes at most one replacement at O(log k), O(n log k) in total, O(k) space.

After all the numbers, the heap holds the k largest and the gatekeeper is the smallest of them, which is the k-th largest.

The k-th largest uses a min-heap because the top must hold "the one that should be eliminated first". Conversely, the k-th smallest uses a max-heap.

import heapq

def find_kth_largest(nums, k):
    heap = []                       # the k largest seen so far; heap[0] is the gatekeeper
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:           # only larger than the gatekeeper gets in
            heapq.heapreplace(heap, x)   # pop the gatekeeper, then push x, in one step
    return heap[0]


assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert find_kth_largest([7], 1) == 7
assert find_kth_largest([2, 2, 2], 2) == 2

heapq.heapreplace(h, x) is heappop(h) followed by heappush(h, x), but with only one sift, so it's faster than the two calls. It removes the old top whether x is larger or smaller, which is why x > heap[0] has to be checked before calling it.

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

What if you use a max-heap of size k. The top becomes the largest of the k. Once full, each pop removes the largest, the heap keeps the k smallest, and the answer is completely backwards. Rule 1: write down who is on top before choosing min or max.

An equivalent version pushes every number first and pops once whenever the heap exceeds k. Same result, except numbers smaller than the gatekeeper also make a trip in and out of the heap.

This approach is online: every number updates the answer right away, without waiting for all the data. If all data is in memory and you only need one answer, quickselect is O(n) on average and O(n²) in the worst case.

Same idea: k-th largest in a stream (LC 703)

Design a class KthLargest. The constructor takes k and an initial array nums; after that, each call add(val) adds val and returns the k-th largest of all numbers so far (repeated values each take a position). The problem guarantees there are at least k numbers after every add.

For example, with k = 3 and initial [4, 5, 8, 2]: after add(3) the numbers are 2, 3, 4, 5, 8, and the 3rd largest is 4; after add(5) they are 2, 3, 4, 5, 5, 8, and the 3rd largest is 5.

The difference from the previous problem: old numbers never go away, and later queries still count them.

Think first: Which part of the gatekeeper heap goes into the constructor and which into add? Can a number smaller than the gatekeeper ever become the answer later? What happens to the heap if the initial array has fewer than k numbers?

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []              # the k largest, gatekeeper on top
        for x in nums:
            self.add(x)             # the initial numbers take the same path as later ones

    def add(self, val):
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]


s = KthLargest(3, [4, 5, 8, 2])
assert s.add(3) == 4
assert s.add(5) == 5
assert s.add(10) == 5
assert s.add(9) == 8

Same idea: k closest points to the origin (LC 973)

This is the problem analyzed in "Before You Code": given points and k, return the k points closest to the origin, in any order. For example, [[1, 3], [-2, 2]] with k = 1 → [[-2, 2]].

Think first: The three questions are already answered: a max-heap storing (-dist², x, y). Two coding details remain. The top is a tuple, so how do you write "the new point is closer than the gatekeeper"? When two points are equally far, what does the tuple compare next, and can that fail?

import heapq

def k_closest(points, k):
    heap = []                       # (-dist², x, y); the top is the farthest of the k
    for x, y in points:
        d = x * x + y * y           # squared distance, no square root
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif d < -heap[0][0]:       # heap[0][0] is the gatekeeper's -d; only closer gets in
            heapq.heapreplace(heap, (-d, x, y))
    return [[x, y] for _, x, y in heap]   # unpack each tuple, drop the distance, keep coordinates


assert sorted(k_closest([[1, 3], [-2, 2]], 1)) == [[-2, 2]]
assert sorted(k_closest([[3, 3], [5, -1], [-2, 4]], 2)) == [[-2, 4], [3, 3]]
assert k_closest([[0, 1]], 1) == [[0, 1]]

Variation: the k most frequent words (LC 692)

The input is a list of lowercase words words and k. Return the k most frequent distinct words, sorted by frequency from high to low; words with the same frequency are sorted in ascending lexicographic order.

For example, ["i", "love", "leetcode", "i", "love", "coding"] with k = 2 → ["i", "love"]: "i" and "love" both appear twice, and on the tie the lexicographically smaller "i" comes first.

Unlike LC 215, you first have to count how often each word appears, and the result must come out in the required order.

Think first: The gatekeeper is "the worst of the top k". In this problem, which of two words is worse? If you push (freq, word) or (-freq, word) into a min-heap, who ends up on top in each case, and is that the "worst" you want?

class WordEntry:
    def __init__(self, word, freq):
        self.word = word
        self.freq = freq

    def __lt__(self, other):        # called by a < b; self is worse than other, so it sits on top
        if self.freq != other.freq:
            return self.freq < other.freq   # lower frequency is worse
        return self.word > other.word       # on a tie, the larger word is worse


assert WordEntry("a", 1) < WordEntry("b", 2)
assert WordEntry("b", 2) < WordEntry("a", 2)
assert not (WordEntry("a", 2) < WordEntry("b", 2))

import heapq
from collections import Counter

def top_k_frequent(words, k):
    heap = []                       # the best k; the worst of them on top
    for word, freq in Counter(words).items():   # Counter: word -> count
        e = WordEntry(word, freq)
        if len(heap) < k:
            heapq.heappush(heap, e)
        elif heap[0] < e:           # the gatekeeper is worse than the newcomer, replace it
            heapq.heapreplace(heap, e)
    res = [heapq.heappop(heap).word for _ in range(len(heap))]
    return res[::-1]                # popped worst to best; the slice [::-1] reverses it


assert top_k_frequent(["i", "love", "leetcode", "i", "love", "coding"], 2) == ["i", "love"]
assert top_k_frequent(["the", "day", "is", "sunny", "the", "the", "the",
                       "sunny", "is", "is"], 4) == ["the", "is", "sunny", "day"]
assert top_k_frequent(["b", "a", "c"], 2) == ["a", "b"]

Step 2 recap

• What it solves: keeping the "top k" while reading the input once, in O(k) space; at the end the top of the heap is the k-th best.
• The key line: elif x > heap[0]: heapq.heapreplace(heap, x). Only what beats the gatekeeper gets in.
• What the variations change: 703 moves the same logic into add; 973 uses -dist² to turn the min-heap into a max-heap; 692 defines "worse" itself with __lt__.
• Easiest mistake: the direction of the heap. First write "the top is the one among these k that should be eliminated first", then decide between a min-heap and storing negatives.

In the first two steps the heap held existing elements. From the next step on, the heap holds only the few candidates that could be the next smallest.

Step 3: k-way merge, the heap holds only each list's head

Problem : merge k sorted arrays ( LC 23 is the linked-list version). (Pro lesson)

Same idea: Design Twitter (LC 355)

Design a class Twitter with four operations: postTweet(userId, tweetId) : the user posts a tweet. (Pro lesson)

Step 3 recap

What it solves : emitting the elements of k individually sorted sequences in global order, in O(n log k). (Pro lesson)

Step 4: Best-first search on an implicit graph, dedup on generation

Problem : in a matrix where every row and every column is increasing, find the k-th smallest number ( LC 378 ). (Pro lesson)

Same idea: the k-th smallest number with only factors 3, 5, 7 (of the form 3^x · 5^y · 7^z with x, y, z all at least 1)

Practice here (original problem) ↗ Given k (k ≥ 1), return the k-th smallest number of the form 3^x · 5^y · 7^z with x, y, z all at least 1:… (Pro lesson)

Step 4 recap

What it solves : the answer lives in an implicit graph that "grows from small to large"; (Pro lesson)

Step 5: Two heaps squeeze the middle

Problem : median of a data stream; addNum adds a number and findMedian returns the current median ( LC 295 ). (Pro lesson)

Step 5 recap

What it solves : numbers arrive one at a time and the median is needed at any moment: add in O(log n), query in O(1). (Pro lesson)

Step 6: Sort + pointer, a candidate enters only once its condition holds

Problem : Car Pooling ( LC 1094 ). trips[i] = [passengers, from, to] , the car drives in one direction with capacity seats; (Pro lesson)

Variation: Single-Threaded CPU (LC 1834)

The input is tasks , where tasks[i] = [enqueue time, processing time] , with task indices starting at 0. (Pro lesson)

Variation: IPO (LC 502)

You start with capital w and can do at most k projects. (Pro lesson)

Variation: Course Schedule III (LC 630)

The input is courses , where courses[i] = [duration, lastDay] . (Pro lesson)

Step 6 recap

What it solves : candidates "unlock" one by one over time or as capital grows, and each time you need the best among those unlocked. (Pro lesson)

Advanced: hold back what was just used

Problem : rearrange a string so no two adjacent characters are equal, or return "" if impossible ( LC 767 ). (Pro lesson)

Same idea: Task Scheduler (LC 621)

The input is a list of tasks tasks , each an uppercase letter naming its kind, and a cooldown n ≥ 0. Each task takes 1 time unit. (Pro lesson)

Same idea: Longest Happy String (LC 1405)

The input is three non-negative integers a, b, c with a + b + c > 0. (Pro lesson)

Advanced recap

What it solves : greedily using whatever has the most left, when something just used can't be used again for a while. (Pro lesson)

All six steps together

Step What the heap holds Who is on top In and out per round Complexity Step 1 every element the max (negated) or the min pop 2 push 1 / pop… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem says it) Translated to the core problem Step LC 1046 smash the two heaviest stones each round max-heap, repeatedly… (Pro lesson)

Common Pitfalls

Treating heapq as a max-heap, or storing negatives and forgetting to negate back. You actually get the minimum, or the answer's sign flips. (Pro lesson)

Say It in the Interview

After confirming the range of k and whether the data comes all at once or one at a time, you can say: I'll keep a min-heap of size k that al… (Pro lesson)