INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP
01
00/15
01 / COVER MODULE 19 · HEAPS
INVARIANT · MODULE 19 · HEAPS
ONLY THE TOP IS IN ORDER

A heap keeps one promise: every parent beats its children, so the best item is always at the root. Nothing else is kept in order, so a push or a pop costs only log n. Ten moves, fifteen problems.

15Problems
6Families
10Units
11Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

INSIDE THE HEAP · 02
KEEP k · 05
GREEDY WITH A HEAP · 03
TWO HEAPS · 02
ONE HEAD PER LIST · 01
TAKE IT BACK LATER · 02
SOLVED HAS A JUDGE LINK
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
03 / MECHANISM UNIT 01 · PUSH

A NEW LEAF CLIMBS

The new value goes in at the end, the one spot that keeps the tree complete. While it beats its parent, the two swap. That is one path from a leaf up, so a push is O(log n).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
04 / MECHANISM UNIT 01 · POP

THE LAST LEAF SINKS

The maximum leaves the root, and the last leaf fills the hole. It swaps with its larger child until both children are smaller. One path down, so a pop is O(log n).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
05 / DRILL UNIT 01 · Sift Up, Sift Down · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Push 8 into the max-heap [9, 5, 7, 1, 3]. What is the array after?

8 goes in at index 5, under 7 at index 2. 8 beats 7, so they swap. Its new parent is 9, which is larger, so it stops.

DRILL 02 · RECALL

Why does a pop move the last leaf into the root, instead of promoting a child?

Promoting children leaves a hole somewhere in the middle of the array. The last leaf is the one item that can move without breaking the shape, and sinking it fixes the order.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
06 / PROBLEM #01 · INSIDE · EASY

Last Stone Weight

EASY inside ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Again and again, take the two heaviest stones, smash them together, and put back what is left.

INTUITION

A max-heap hands over the heaviest stone in O(log n) and takes a new one back in O(log n). Re-sorting after every smash would cost O(n log n) a round.

STEPS
  1. Put every stone in a max-heap
  2. Pop the heaviest, y, and then the next, x
  3. If they differ, push y − x back
  4. When at most one stone is left, return it, or 0
BRUTEO(n² log n) re-sorting after every smash
→
OPTIMALO(n log n)
↕ SCROLL
int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> h(stones.begin(), stones.end());   // a max-heap
    while (h.size() > 1) {
        int y = h.top(); h.pop();          // the heaviest
        int x = h.top(); h.pop();          // the next heaviest
        if (y != x) h.push(y - x);         // what is left of y goes back
    }
    return h.empty() ? 0 : h.top();
}
TIMEO(n log n)at most n − 1 rounds, each a few heap moves of O(log n)
SPACEO(n)the heap
TRAP

The library's default heap. Python's heapq and Java's PriorityQueue put the smallest on top. Without negatives or a reversed comparator, the two lightest stones get smashed.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
07 / DRILL UNIT 01 · Sift Up, Sift Down · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

lastStoneWeight([2, 7, 4, 1, 8, 1])?

8 and 7 leave 1; then 4 and 2 leave 2; then 2 and 1 leave 1; then 1 and 1 cancel. One stone of weight 1 is left.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
08 / MECHANISM UNIT 02 · HEAPIFY IN O(N)

EVERY PARENT SINKS, THE LAST ONE FIRST

Leaves are heaps already. Sink each parent, from n / 2 − 1 down to 0, into the heaps below it. Most parents sit low and sink little, so the whole job is O(n).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
09 / DRILL UNIT 02 · Heapify in O(n) · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

heapify([1, 5, 3, 4, 2]) into a max-heap?

Index 1 holds 5, above 4 and 2, so it stays. Then 1 at the root swaps with 5, and sinks once more, swapping with 4.

DRILL 02 · RECALL

Heapify sinks n / 2 parents, each up to log n levels. Why is it O(n), not O(n log n)?

Half the nodes are leaves, a quarter sink one level, an eighth two levels, and so on. That sum stays below n.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
10 / PROBLEM #02 · INSIDE · MED

Heap Sort

MED inside ▶ SOLVE ON GEEKSFORGEEKSGeeksforGeeks rates it Medium. Sort an Array (LC 912) takes the same code; it belongs to the sorting deck.
SIGNAL — WHAT GIVES IT AWAY

Sort the array by heap sort, in place: O(n log n) time and O(1) extra space.

INTUITION

Heapify the array into a max-heap in O(n). The maximum is then at index 0. Swap it to the end, where it belongs, and sink the new root into a heap one shorter. Repeat until one item is left.

STEPS
  1. Sink every parent, from n / 2 − 1 down to 0, and the array is a max-heap
  2. Swap a[0], the maximum, with the last item of the heap
  3. The heap is now one shorter; sink the new root inside it
  4. Repeat until the heap holds one item
BRUTEO(n²) selection sort, scanning for the maximum every time
→
OPTIMALO(n log n)
↕ SCROLL
void sink(vector<int>& a, int n, int i) {   // unit 1's sift down, on a[0..n)
    while (true) {
        int l = 2 * i + 1, r = l + 1, big = i;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(a[i], a[big]);
        i = big;
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int s = n / 2 - 1; s >= 0; s--) sink(arr, n, s);   // heapify, O(n)
    for (int end = n - 1; end > 0; end--) {
        swap(arr[0], arr[end]);            // the maximum goes to its final place
        sink(arr, end, 0);                 // the heap is now arr[0..end)
    }
}
TIMEO(n log n)O(n) to heapify, then n sinks of O(log n)
SPACEO(1)in place; the sink loop needs no stack
TRAP

Sinking into the sorted tail. After each swap the end of the array is sorted and no longer heap. Pass the shrinking size to sink, not n, or the maxima already placed are pulled back up.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
11 / DRILL UNIT 02 · Heapify in O(n) · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Heap sort swaps a[0] to the end of the heap and sinks the new root. Into what?

The item just swapped to the end is in its final place, so it is no longer part of the heap. Sinking into the whole array would pull it back up.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
12 / MECHANISM UNIT 03 · KEEP K, DROP THE REST

THE SMALLEST OF k + 1 LEAVES

Keep the k largest in a min-heap. Each new value goes in, and with k + 1 held, the smallest cannot be in the top k. At the end the root is the kth largest.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
13 / DRILL UNIT 03 · Keep k, Drop the Rest · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

findKthLargest([7, 1, 5, 3, 9], 3)?

The three largest are 9, 7 and 5. The heap of three ends with 5 at its root.

DRILL 02 · RECALL

To keep the k largest, why a min-heap and not a max-heap?

When k + 1 values are held, the one that must leave is the smallest of them. Only a min-heap has it on top, ready to pop.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
14 / PROBLEM #03 · KEEPK · MED

Kth Largest Element in an Array

MED keepk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The kth largest value in an unsorted array. The kth largest, not the kth distinct.

INTUITION

Keep a min-heap of the k largest values seen so far. Each new value goes in, and when the heap holds k + 1, the smallest of them cannot be in the top k, so it leaves. At the end the root is the kth largest.

STEPS
  1. A min-heap h, empty
  2. Push each value
  3. If h holds k + 1 values, pop the smallest
  4. Return the root
BRUTEO(n log n) sorting everything
→
OPTIMALO(n log k)
↕ SCROLL
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> h;   // the k largest, smallest on top
    for (int x : nums) {
        h.push(x);
        if ((int)h.size() > k) h.pop();    // the smallest of k + 1 is not in the top k
    }
    return h.top();                        // the smallest of the k largest
}
TIMEO(n log k)n pushes and at most n pops on a heap of k + 1
SPACEO(k)the heap of k
TRAP

The heap facing the wrong way. A max-heap of size k throws away the largest values, the very ones being kept. The heap that holds the top k must put the smallest of them on top, where it can leave.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
15 / PROBLEM #04 · KEEPK · EASY

Kth Largest Element in a Stream

EASY keepk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Values arrive one at a time, and after each one, report the kth largest so far.

INTUITION

Row 3's heap, kept between calls. A value below the kth largest can never matter again, because the stream only adds values above it. Each call is one push and at most one pop.

STEPS
  1. The constructor adds the starting values one by one
  2. add pushes the new value
  3. If the heap holds k + 1, pop the smallest
  4. Return the root
BRUTEO(n) per add, inserting into a sorted list
→
OPTIMALO(log k) per add
↕ SCROLL
class KthLargest {
    priority_queue<int, vector<int>, greater<int>> h;   // the k largest, smallest on top
    int k;
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int val) {
        h.push(val);
        if ((int)h.size() > k) h.pop();
        return h.top();                    // the kth largest so far
    }
};
TIMEO(log k) per addone push and at most one pop on a heap of k + 1
SPACEO(k)the heap of k
TRAP

Keeping every value. A sorted list of the whole stream answers each call, but each insert costs O(n) and the memory never stops growing.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
16 / PROBLEM #05 · KEEPK · MED

K Closest Points to Origin

MED keepk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The k points nearest the origin, in any order.

INTUITION

Row 3 with distance as the value, and the heap facing the other way. Keep the k nearest in a max-heap of distance, so the farthest of them is on top, ready to leave.

STEPS
  1. For each point, its squared distance d = x² + y²
  2. Push (d, index) into a max-heap
  3. If it holds k + 1, pop the farthest
  4. Return the points left in the heap
BRUTEO(n log n) sorting by distance
→
OPTIMALO(n log k)
↕ SCROLL
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<pair<int, int>> h;      // (distance², index): the farthest on top
    for (int i = 0; i < (int)points.size(); i++) {
        int d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        h.push({d, i});
        if ((int)h.size() > k) h.pop();    // the farthest of k + 1 is out
    }
    vector<vector<int>> out;
    while (!h.empty()) { out.push_back(points[h.top().second]); h.pop(); }
    return out;
}
TIMEO(n log k)n pushes and pops on a heap of k + 1
SPACEO(k)the heap of k
TRAP

Taking the square root. It costs time and adds rounding error, and it never changes which point is nearer. Compare squared distances.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
17 / DRILL UNIT 03 · Keep k, Drop the Rest · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

kClosest compares x² + y² and never takes a square root. Why is that safe?

For non-negative numbers, a < b exactly when √a < √b. The order is all the heap needs, and the squares are exact.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
18 / MECHANISM UNIT 04 · A KEY AND A TIE-BREAK

THE COMPARISON CARRIES THE WHOLE ORDER

More copies ranks higher, and on a tie the earlier word in the alphabet. With the worst word on top, the worst of k + 1 leaves, and the rest pop out worst first.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
19 / DRILL UNIT 04 · A Key and a Tie-Break · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

topKFrequent(["a", "b", "a", "c", "b", "d"], 2)?

a and b both appear twice, and a comes first in the alphabet. c and d appear once.

DRILL 02 · RECALL

In the heap that keeps the worst word on top, which of two equally common words is the worse?

The answer lists equal counts alphabetically, so the later word ranks lower. It is the one that leaves first.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
20 / PROBLEM #06 · KEEPK · MED

Top K Frequent Words

MED keepk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The k most frequent words, most frequent first, with equal counts in alphabetical order.

INTUITION

Count, then keep a heap of k words with the worst on top. A word is worse if it is rarer, or equally common and later in the alphabet. The worst of k + 1 leaves; popping what is left gives the answer worst first, so fill it from the back.

STEPS
  1. Count every word in a map
  2. Order words by count, then alphabetically, with the worst on top
  3. Push each word; if the heap holds k + 1, pop the worst
  4. Pop the rest into the answer from the back
BRUTEO(n log n) sorting every distinct word
→
OPTIMALO(n log k)
↕ SCROLL
vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> cnt;
    for (auto& w : words) cnt[w]++;
    auto better = [&](const string& a, const string& b) {
        return cnt[a] != cnt[b] ? cnt[a] > cnt[b] : a < b;
    };
    priority_queue<string, vector<string>, decltype(better)> h(better);   // the worst on top
    for (auto& e : cnt) {
        h.push(e.first);
        if ((int)h.size() > k) h.pop();    // the worst of k + 1 leaves
    }
    vector<string> out(k);
    for (int i = k - 1; i >= 0; i--) { out[i] = h.top(); h.pop(); }
    return out;
}
TIMEO(n log k)counting is O(n); m distinct words each cost O(log k)
SPACEO(n)the counts
TRAP

The tie-break pointing the wrong way. In a heap that keeps the worst on top, the worse of two equal counts is the word that comes later in the alphabet. Flip either half of the comparison and the wrong word survives.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
21 / PROBLEM #07 · KEEPK · MED

Constructing the Array

MED keepk ▶ SOLVE ON CODEFORCESCodeforces 1353D, rated 1600.
SIGNAL — WHAT GIVES IT AWAY

Fill an array by always splitting the longest run of zeros, taking the leftmost on a tie, at its middle.

INTUITION

Keep the runs of zeros in a heap ordered by length, then by left end. Each action pops the best run, writes i at its middle, and pushes back the two halves that are left.

STEPS
  1. A heap of runs: (−length, left end), so the longest and then the leftmost is on top
  2. Start with the run [1, n]
  3. For i = 1 to n, pop a run and write i at m = (l + r) / 2
  4. Push [l, m − 1] and [m + 1, r] when they are not empty
BRUTEO(n²) scanning for the longest run of zeros at every action
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        vector<int> a(n + 1);
        priority_queue<pair<int, int>> h;  // (length, −left end): longest, then leftmost
        h.push({n, -1});
        for (int i = 1; i <= n; i++) {
            int len = h.top().first, l = -h.top().second; h.pop();
            int r = l + len - 1, m = (l + r) / 2;   // the left middle when len is even
            a[m] = i;
            if (m > l) h.push({m - l, -l});
            if (r > m) h.push({r - m, -(m + 1)});
        }
        for (int i = 1; i <= n; i++) printf("%d ", a[i]);
        puts("");
    }
}
TIMEO(n log n)n pops and at most 2n pushes
SPACEO(n)the array and the heap of runs
TRAP

Ordering the runs by length alone. Equal runs must come out leftmost first. A heap that compares only lengths returns them in any order, and the array comes out wrong on the first tie.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
22 / DRILL UNIT 04 · A Key and a Tie-Break · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Constructing the Array with n = 4. What is printed?

Action 1 splits [1, 4] at its left middle, 2. Then [3, 4] is the longest run: 2 goes at 3. [1, 1] is leftmost of the runs of one: 3 goes there, and 4 at position 4.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
23 / MECHANISM UNIT 05 · MOST LEFT GOES FIRST

TWO DIFFERENT LETTERS A ROUND

Pop the two letters with the most copies left and place both. Each goes back with one fewer. A letter left over at the end fits only if one copy of it is left.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
24 / DRILL UNIT 05 · Most Left Goes First

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

reorganizeString("aaab")?

Three a's need two other letters between them, and there is only one b. The last round leaves (2, a) in the heap, so the answer is empty.

DRILL 02 · RECALL

When is a rearrangement impossible?

The copies of one letter need a different letter between each pair. That fits only when the letter fills at most every other position, ⌈n / 2⌉ of them.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
25 / PROBLEM #08 · GREEDY · MED

Reorganize String

MED greedy ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Rearrange the letters so that no two neighbours are equal, or return "" if that cannot be done.

INTUITION

Each round, place the two letters with the most copies left, which are two different letters. The one with the most left is the one that can run out of room, so it goes as early as possible. If one letter is left over at the end with two or more copies, they would touch.

STEPS
  1. Count the letters; push (count, letter) into a max-heap
  2. While two or more letters are left, pop two and append both
  3. Push each back with one fewer, if any are left
  4. If one letter is left, append it if it has one copy, else return ""
BRUTEO(n! · n) trying every arrangement
→
OPTIMALO(n log 26)
↕ SCROLL
string reorganizeString(string s) {
    map<char, int> cnt;
    for (char c : s) cnt[c]++;
    priority_queue<pair<int, char>> h;     // (count left, letter): the most on top
    for (auto& e : cnt) h.push({e.second, e.first});
    string out;
    while (h.size() >= 2) {
        auto a = h.top(); h.pop();         // the most left
        auto b = h.top(); h.pop();         // a different letter
        out += a.second; out += b.second;
        if (--a.first) h.push(a);
        if (--b.first) h.push(b);
    }
    if (h.size()) {
        if (h.top().first > 1) return "";  // it would sit beside itself
        out += h.top().second;
    }
    return out;
}
TIMEO(n log 26)n letters placed, each a heap move on at most 26 items
SPACEO(26)the counts and the heap
TRAP

One letter per round. Popping only the top, placing it and pushing it back can place the same letter twice in a row. Pop two different letters before either goes back.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
26 / MECHANISM UNIT 06 · WAIT OUT A COOLDOWN

A HEAP OF THE FREE, A QUEUE OF THE COOLING

Each unit, a task whose cooldown has ended goes back into the heap, and then the free task with the most runs left runs. With nothing free, the unit is idle.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
27 / DRILL UNIT 06 · Wait Out a Cooldown

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

leastInterval([A, A, A, B, B, B], n = 2)?

A B idle A B idle A B. Each A needs two units after it, and B fills only one of them.

DRILL 02 · RECALL

A task that just ran goes to a queue, not straight back into the heap. Why?

Back in the heap it could be popped at the very next unit. The queue holds it until time + n + 1, and tasks leave the queue in the order they ran.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
28 / PROBLEM #09 · GREEDY · MED

Task Scheduler

MED greedy ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Run tasks one per unit of time, where the same task needs n units of something else or idle between two runs. The fewest units in total.

INTUITION

At each unit, run the free task with the most runs left; it is the one that needs the most gaps. A task that just ran waits in a queue, in the order it ran, until its cooldown ends, then goes back into the heap. A unit with nothing free is idle.

STEPS
  1. Count runs per task; push the counts into a max-heap
  2. Each unit of time: if the queue's front is free now, it goes back into the heap
  3. Pop the most runs left and run it; if runs remain, queue it, free at time + n + 1
  4. Stop when the heap and the queue are both empty
BRUTEexponential, trying every schedule
→
OPTIMALO(m log 26)
↕ SCROLL
int leastInterval(vector<char>& tasks, int n) {
    int cnt[26] = {};
    for (char t : tasks) cnt[t - 'A']++;
    priority_queue<int> h;                 // runs left, the most on top
    for (int c : cnt) if (c) h.push(c);
    queue<pair<int, int>> wait;            // (free at, runs left), in the order they ran
    int time = 0;
    while (!h.empty() || !wait.empty()) {
        time++;
        if (!wait.empty() && wait.front().first == time) {
            h.push(wait.front().second); wait.pop();   // cooled down
        }
        if (!h.empty()) {
            int c = h.top() - 1; h.pop();  // run the task with the most runs left
            if (c) wait.push({time + n + 1, c});
        }                                  // otherwise this unit is idle
    }
    return time;
}
TIMEO(m log 26)m units of time, at most tasks · (n + 1), each a heap move
SPACEO(26)the heap and the queue hold at most 26 tasks
TRAP

Running any free task. An order that ignores the counts can leave the most frequent task with too few gaps at the end, and each missing gap becomes an idle unit.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
29 / MECHANISM UNIT 07 · THE SMALLEST STARTS A GROUP

THE SMALLEST CARD HAS NO CHOICE

Nothing below the smallest card is left, so it starts a run. Take each value of the run from the counts. A value used up must be the smallest left, or a smaller card is stranded.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
30 / DRILL UNIT 07 · The Smallest Starts a Group

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

isNStraightHand([1, 1, 2, 2, 3, 4], 3)?

1 starts a run 1, 2, 3, and the 3 is then used up while a 1 is still the smallest left. That 1 would need a second 3, so the hand cannot be split.

DRILL 02 · RECALL

A count reaches zero, but that value is not the heap's root. What does that mean?

The root is smaller and still has cards. Every run through it would need the value just used up, so it can never be grouped.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
31 / PROBLEM #10 · GREEDY · MED

Hand of Straights

MED greedy ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Split the cards into groups of groupSize consecutive values, every card used once.

INTUITION

The smallest card left cannot join a run that starts lower, because nothing lower is left, so it starts a run. Take that run's values from the counts. A value whose count reaches zero must be the smallest left, or a smaller one is stranded.

STEPS
  1. Count each value; a min-heap holds the distinct values
  2. s = the root starts a run of s, s + 1, …, s + groupSize − 1
  3. Each value in the run must have a card; take one
  4. A count that reaches zero must be the root, and it is popped
BRUTEexponential, trying every way to group the cards
→
OPTIMALO(n log n)
↕ SCROLL
bool isNStraightHand(vector<int>& hand, int groupSize) {
    if (hand.size() % groupSize) return false;
    map<int, int> cnt;
    for (int x : hand) cnt[x]++;
    priority_queue<int, vector<int>, greater<int>> h;   // the smallest value on top
    for (auto& e : cnt) h.push(e.first);
    while (!h.empty()) {
        int s = h.top();                   // nothing smaller is left: s starts a run
        for (int x = s; x < s + groupSize; x++) {
            if (cnt[x] == 0) return false; // a gap in the run
            if (--cnt[x] == 0) {
                if (x != h.top()) return false;   // a smaller value would be stranded
                h.pop();
            }
        }
    }
    return true;
}
TIMEO(n log n)n cards taken, and each distinct value popped once
SPACEO(n)the counts and the heap
TRAP

Starting a run at any card. A run started in the middle can strand a smaller card with no run left to join. Only the smallest card left has no choice to make.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
32 / MECHANISM UNIT 08 · TWO HEAPS

THE MEDIAN SITS BETWEEN TWO TOPS

lo holds the smaller half with its maximum on top, and hi the larger half with its minimum on top. Every number passes through lo into hi, and hi hands one back if it grows too big.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
33 / DRILL UNIT 08 · Two Heaps · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Add 4, 1, 7 and 3 to a MedianFinder. findMedian()?

Sorted, they are 1, 3, 4, 7. The sizes are equal, so the median is (3 + 4) / 2.

DRILL 02 · RECALL

After each addNum, which of these always holds?

The rebalance moves hi's top back whenever hi is bigger, so lo is never smaller and never more than one bigger.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
34 / PROBLEM #11 · TWO · HARD

Find Median from Data Stream

HARD two ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Numbers arrive one at a time, and at any moment report the median of all of them so far.

INTUITION

Keep the smaller half in a max-heap and the larger half in a min-heap, with lo never smaller than hi and never more than one bigger. The median is lo's top, or the average of the two tops. Routing each number through lo and then hi keeps every value in lo at most every value in hi.

STEPS
  1. Push the number into lo
  2. Move lo's maximum to hi
  3. If hi now holds more than lo, move hi's minimum back
  4. Median: lo's top if lo is bigger, else the average of both tops
BRUTEO(n) per add, inserting into a sorted list
→
OPTIMALO(log n) per add
↕ SCROLL
class MedianFinder {
    priority_queue<int> lo;                              // the smaller half, max on top
    priority_queue<int, vector<int>, greater<int>> hi;   // the larger half, min on top
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();       // lo's maximum crosses over
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};
TIMEO(log n) per adda few heap moves per addNum; findMedian reads two tops in O(1)
SPACEO(n)both heaps
TRAP

Choosing a side by one comparison. Comparing the number with lo's top and pushing it there or into hi, then rebalancing by size, can move a value to the wrong side. Passing every number through lo and then hi cannot.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
35 / PROBLEM #12 · TWO · HARD

IPO

HARD two ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Start with capital w and finish at most k projects, each needing capital to start and adding its profit. The most capital at the end.

INTUITION

Two heaps. One holds the projects still too dear, cheapest first. Before each pick, every project w can now afford moves to the other, a max-heap of profits, and the biggest profit is taken. Capital only grows, so a project once affordable stays affordable.

STEPS
  1. locked is a min-heap of (capital, profit), and ready a max-heap of profits
  2. Up to k times, move every project with capital ≤ w from locked to ready
  3. If ready is empty, stop, since w can never grow
  4. Otherwise take ready's top and add its profit to w
BRUTEO(n^k) trying every sequence of k projects
→
OPTIMALO(n log n)
↕ SCROLL
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    typedef pair<int, int> P;              // (capital needed, profit)
    priority_queue<P, vector<P>, greater<P>> locked;   // the cheapest to start on top
    priority_queue<int> ready;             // profits w can afford, the largest on top
    for (int i = 0; i < (int)profits.size(); i++) locked.push({capital[i], profits[i]});
    while (k--) {
        while (!locked.empty() && locked.top().first <= w) {
            ready.push(locked.top().second); locked.pop();   // now affordable
        }
        if (ready.empty()) break;          // nothing affordable: w cannot grow
        w += ready.top(); ready.pop();     // the most profitable project
    }
    return w;
}
TIMEO(n log n)each project moves between the heaps once
SPACEO(n)the two heaps
TRAP

Taking the most profitable project overall. It may need more capital than w holds. Only the projects w can already afford compete, and that set only grows.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
36 / DRILL UNIT 08 · Two Heaps · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

findMaximizedCapital(k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1])?

Only project 0 is affordable: w becomes 1. Now projects 1 and 2 both are, and 3 is the larger profit: w becomes 4.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
37 / MECHANISM UNIT 09 · ONE HEAD PER LIST

ONLY THE SMALLEST HEAD MOVES THE LOW END

One head per list sits in a min-heap, and hi is the largest head, so [smallest, hi] covers every list. Pop the smallest, record the range, and push the next value of its list.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
38 / DRILL UNIT 09 · One Head per List

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

smallestRange([[1, 9], [4, 6], [5, 8]])?

[1, 5] has width 4, and so does [5, 9], which is not narrower. Then 6 is the smallest head, with 9 the largest: [6, 9], width 3. List 1 then runs out.

DRILL 02 · RECALL

Why does the loop stop as soon as one list runs out?

The list's last value has just left the heap. Any range with a larger low end holds nothing from that list, so no later range qualifies.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
39 / PROBLEM #13 · HEADS · HARD

Smallest Range Covering Elements from K Lists

HARD heads ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

k sorted lists. The narrowest range that holds at least one number from every list, the smaller start on a tie.

INTUITION

Keep one head per list in a min-heap and track hi, the largest head. The range [smallest head, hi] covers every list. Only replacing the smallest head can raise the low end, so pop it, record the range, and push the next value of its list. When a list runs out, no range without it exists.

STEPS
  1. Push each list's first value; hi = the largest of them
  2. Pop the smallest head v; the range [v, hi] covers every list
  3. Keep it if it is narrower than the best
  4. If v's list has a next value, push it and raise hi; else stop
BRUTEO(n² · k) trying every pair of values as the ends
→
OPTIMALO(n log k)
↕ SCROLL
vector<int> smallestRange(vector<vector<int>>& nums) {
    typedef array<int, 3> T;               // (value, list, index)
    priority_queue<T, vector<T>, greater<T>> h;   // the smallest head on top
    int hi = INT_MIN;
    for (int i = 0; i < (int)nums.size(); i++) {
        h.push({nums[i][0], i, 0});
        hi = max(hi, nums[i][0]);
    }
    vector<int> best = {0, INT_MAX};
    while (true) {
        T t = h.top(); h.pop();            // the smallest head leaves
        if (hi - t[0] < best[1] - best[0]) best = {t[0], hi};
        if (t[2] + 1 == (int)nums[t[1]].size()) break;   // its list ran out
        int v = nums[t[1]][t[2] + 1];
        h.push({v, t[1], t[2] + 1});
        hi = max(hi, v);
    }
    return best;
}
TIMEO(n log k)each of the n values is pushed and popped once, on a heap of k
SPACEO(k)one head per list
TRAP

Advancing the list with the largest head. That can only raise hi, while the low end stays where it is, so the range never narrows.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
40 / MECHANISM UNIT 10 · TAKE IT BACK LATER

LADDERS GO TO THE TALLEST CLIMBS

Every climb takes a ladder for now. When there are more climbs than ladders, the smallest climb on a ladder pays in bricks instead. The walk stops when bricks run out.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
41 / DRILL UNIT 10 · Take It Back Later · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

furthestBuilding([1, 5, 1, 2, 3, 4, 10000], bricks = 4, ladders = 1)?

The ladder keeps the climb of 4 while three climbs of 1 use 3 bricks. The climb of 9996 then takes the ladder, the 4 moves to bricks, and bricks go below zero at building 5.

DRILL 02 · RECALL

The heap holds more climbs than there are ladders. Which climb pays in bricks?

A ladder saves as many bricks as its climb is tall. Moving the smallest climb to bricks costs the fewest bricks.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
42 / PROBLEM #14 · REGRET · MED

Furthest Building You Can Reach

MED regret ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Climb from building to building with some bricks (one per unit of climb) and some ladders (one per climb, any height). How far can you get?

INTUITION

A ladder saves as many bricks as the climb is tall, so ladders belong on the tallest climbs. Put every climb on a ladder for now and keep those climbs in a min-heap. When there are more climbs than ladders, the smallest of them pays in bricks instead; when bricks run out, stop.

STEPS
  1. For each step up, d = the climb
  2. Push d into a min-heap of climbs on ladders
  3. If the heap holds more than the ladders, pop the smallest and pay it in bricks
  4. If bricks go below zero, this building is as far as you get
BRUTEO(2ⁿ) trying every way to place the ladders
→
OPTIMALO(n log L)
↕ SCROLL
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<int>> lad;   // climbs on ladders, smallest on top
    for (int i = 0; i + 1 < (int)heights.size(); i++) {
        int d = heights[i + 1] - heights[i];
        if (d <= 0) continue;              // down or level: free
        lad.push(d);                       // a ladder, for now
        if ((int)lad.size() > ladders) {   // one too many: the smallest climb takes bricks
            bricks -= lad.top(); lad.pop();
            if (bricks < 0) return i;
        }
    }
    return heights.size() - 1;
}
TIMEO(n log L)n pushes on a heap of at most L + 1, for L ladders
SPACEO(L)the climbs on ladders
TRAP

Paying in bricks first. Spending bricks on each climb as it comes and saving ladders for when bricks run out puts the ladders on whatever climbs come last, not on the tallest.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
43 / PROBLEM #15 · REGRET · MED

Playlist

MED regret ▶ SOLVE ON CODEFORCESCodeforces 1140C, rated 1600.
SIGNAL — WHAT GIVES IT AWAY

Choose at most k songs to maximise (total length) × (smallest beauty among them).

INTUITION

Sort by beauty, most beautiful first. Then the song just read has the smallest beauty of all songs read so far, and with it fixed as the minimum, the best set is the k longest songs read. A min-heap of lengths keeps those k and their sum.

STEPS
  1. Sort the songs by beauty, descending
  2. Push each length into a min-heap and add it to the sum
  3. If the heap holds k + 1, pop the shortest and subtract it
  4. best = max(best, sum × this song's beauty)
BRUTEO(2ⁿ) trying every set of at most k songs
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; scanf("%d %d", &n, &k);
    vector<pair<int, int> > s(n);          // (beauty, length)
    for (int i = 0; i < n; i++) scanf("%d %d", &s[i].second, &s[i].first);
    sort(s.rbegin(), s.rend());            // the most beautiful first
    priority_queue<int, vector<int>, greater<int> > kept;   // lengths, the shortest on top
    long long sum = 0, best = 0;
    for (int i = 0; i < n; i++) {
        kept.push(s[i].second); sum += s[i].second;
        if ((int)kept.size() > k) { sum -= kept.top(); kept.pop(); }   // drop the shortest
        best = max(best, sum * s[i].first);   // the smallest beauty so far
    }
    printf("%lld\n", best);
}
TIMEO(n log n)the sort, then n pushes on a heap of k + 1
SPACEO(n)the songs and the heap
TRAP

Overflow in the answer. The sum of 3·10⁵ lengths up to 10⁶, times a beauty up to 10⁶, is far past 32 bits. Keep the sum and the product in 64-bit integers.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
44 / DRILL UNIT 10 · Take It Back Later · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Playlist with k = 2 and songs (length, beauty) = (4, 7), (15, 1), (3, 6), (6, 8)?

Read by beauty, highest first: lengths 6 and 4 with beauty 7 give 10 × 7 = 70. Adding beauty 6 keeps the same two lengths at a lower beauty.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
45 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Ten moves, and each has a phrase in the statement that gives it away.

ALWAYS THE LARGEST OR SMALLEST, WHILE ITEMS COME AND GO

a heap: push and pop in O(log n), the top in O(1)

SIFT UP, SIFT DOWNO(log n)
SORT IN PLACE, OR TURN AN ARRAY INTO A HEAP

sink every parent, the last one first

HEAPIFYO(n)
THE kTH LARGEST, OR THE k BEST OF MANY

a heap of k with the worst kept on top

KEEP kO(n log k)
THE TOP k, WITH TIES IN A SET ORDER

every rule of the order goes in the comparison

KEY AND TIE-BREAKO(n log k)
NO TWO EQUAL NEIGHBOURS

place the two letters with the most left each round

MOST LEFT FIRSTO(n log 26)
THE SAME TASK NEEDS A GAP BEFORE IT RUNS AGAIN

a heap of free tasks, a queue of cooling ones

COOLDOWNO(m log 26)
SPLIT INTO RUNS OF CONSECUTIVE VALUES

the smallest value left starts a run

SMALLEST STARTSO(n log n)
A MEDIAN OF A STREAM, OR TWO POOLS THAT FEED EACH OTHER

two heaps whose tops meet in the middle

TWO HEAPSO(log n)
k SORTED LISTS READ AT ONCE

one head per list; the smallest leaves

ONE HEAD PER LISTO(n log k)
A LIMITED SUPPLY OF A BETTER OPTION

give it out freely, then trade the worst back

TAKE IT BACKO(n log L)
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
46 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Merge k sorted arrays into one sorted array. Which move?

Keep each array's next value in a min-heap. The smallest head goes to the output and its array's next value takes its place. It is Merge k Sorted Lists (linked lists 3) on arrays.

DRILL 02 · TRANSFER

The k most frequent numbers, in any order. Which move?

Count, then keep a min-heap of k by count, so the least frequent of k + 1 leaves. It is Top K Frequent Elements (hashing and prefix sums), unit 4 without a tie-break.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
47 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Rearrange a string so that equal letters are at least d positions apart. Which move?

Unit 6 with a cooldown of d − 1: place the free letter with the most copies left, and queue it until it may be used again.

DRILL 02 · RECALL

Why does a push or a pop cost O(log n)?

A complete tree of n items has about log n levels. Sift up and sift down each walk one path between the root and a leaf, with at most one swap per level.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
48 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

THE LIBRARY'S HEAP FACES THE OTHER WAY

C++'s priority_queue keeps the largest on top. Python's heapq and Java's PriorityQueue keep the smallest. Negate, or pass a comparator, every time you change language.

A MAX-HEAP TO KEEP THE k LARGEST

The item that leaves must be the worst one kept, so it has to sit on top. Keeping the k largest needs a min-heap, and keeping the k smallest needs a max-heap.

A TIE-BREAK LEFT OUT OF THE COMPARISON

When equal keys must leave in a set order, as in Top K Frequent Words or Constructing the Array, that order has to be part of the comparison. A heap does not keep the order items arrived in.

READING THE HEAP AS IF IT WERE SORTED

Only the root is in order. Printing the heap's array, or iterating over a priority queue, does not give sorted output. Pop it to get sorted order.

CHANGING AN ITEM INSIDE THE HEAP

A heap cannot find an item in the middle, let alone update it. Push a fresh copy and skip stale ones as they reach the top.

OVERFLOW IN A SUM OR A PRODUCT

Playlist's answer can pass 10¹⁷, and a sum of many values can pass 2³¹. Keep such sums and products in 64-bit integers.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
49 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Ten moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Sift up, sift down
O(log n)
O(1)
a new leaf climbs; the last leaf takes the root and sinks
Heapify
O(n)
O(1)
sink every parent, the last first; heap sort is O(n log n)
Keep k
O(n log k)
O(k)
the worst kept is on top and leaves when k + 1 are held
Key and tie-break
O(n log k)
O(n)
the comparison carries every rule of the order
Most left first
O(n log 26)
O(26)
pop two different letters, push both back
Cooldown
O(m log 26)
O(26)
a heap of the free, a queue of the cooling
Smallest starts a run
O(n log n)
O(n)
the smallest value left has no choice
Two heaps
O(log n) per add
O(n)
lo's max ≤ hi's min; the answer is on the tops
One head per list
O(n log k)
O(k)
the smallest head leaves; its list's next enters
Take it back later
O(n log L)
O(L)
keep the choices in a heap; trade the worst back
INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
50 / CLOSE MODULE 19 · HEAPS

PUSH IT YOURSELF

A new leaf climbed and the last leaf sank; every parent sank once to build a heap; the smallest of k + 1 left; a comparison carried a tie-break; the two letters with the most left were placed; a cooling task waited in a queue; the smallest card started a run; two heaps met at the median; the smallest head made way for its list's next value; and a ladder was traded back for bricks. Merge k Sorted Lists (linked lists 3) is unit 9 on linked lists, Top K Frequent Elements (hashing and prefix sums) is unit 4 without a tie-break, and Sort an Array (sorting) takes row 2's heap sort as it stands.

00%
OF THIS DECK SOLVED
← ALL TOPICS← GENERAL TREESMONOTONIC STACK & DEQUE →

Module 19. Fifteen problems: twelve on LeetCode, two on Codeforces and one on GeeksforGeeks. Next in the sheet: tries.

INVARIANT · HEAPS · THE BEST ONE, ALWAYS ON TOP · HEAPS
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 19 · HEAPS

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.