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.
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.
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 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).
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.
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.
Again and again, take the two heaviest stones, smash them together, and put back what is left.
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.
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(); }
public int lastStoneWeight(int[] stones) { PriorityQueue<Integer> h = new PriorityQueue<>(Collections.reverseOrder()); // a max-heap for (int s : stones) h.add(s); while (h.size() > 1) { int y = h.poll(); // the heaviest int x = h.poll(); // the next heaviest if (y != x) h.add(y - x); // what is left of y goes back } return h.isEmpty() ? 0 : h.peek(); }
import heapq def lastStoneWeight(stones): h = [-s for s in stones] # heapq is a min-heap, so store negatives heapq.heapify(h) while len(h) > 1: y = -heapq.heappop(h) # the heaviest x = -heapq.heappop(h) # the next heaviest if y != x: heapq.heappush(h, -(y - x)) # what is left of y goes back return -h[0] if h else 0
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.
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.
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).
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.
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.
Sort the array by heap sort, in place: O(n log n) time and O(1) extra space.
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.
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) } }
private void sink(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; int t = a[i]; a[i] = a[big]; a[big] = t; i = big; } } public void heapSort(int arr[]) { int n = arr.length; for (int s = n / 2 - 1; s >= 0; s--) sink(arr, n, s); // heapify, O(n) for (int end = n - 1; end > 0; end--) { int t = arr[0]; arr[0] = arr[end]; arr[end] = t; // the maximum goes to its final place sink(arr, end, 0); // the heap is now arr[0..end) } }
def heapSort(arr): def sink(n, i): # unit 1's sift down, on arr[0..n) while True: l, r, big = 2 * i + 1, 2 * i + 2, i if l < n and arr[l] > arr[big]: big = l if r < n and arr[r] > arr[big]: big = r if big == i: return arr[i], arr[big] = arr[big], arr[i] i = big n = len(arr) for s in range(n // 2 - 1, -1, -1): # heapify, O(n) sink(n, s) for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] # the maximum goes to its final place sink(end, 0) # the heap is now arr[0..end)
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.
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.
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.
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.
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.
The kth largest value in an unsorted array. The kth largest, not the kth distinct.
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.
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 }
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> h = new PriorityQueue<>(); // the k largest, smallest on top for (int x : nums) { h.add(x); if (h.size() > k) h.poll(); // the smallest of k + 1 is not in the top k } return h.peek(); // the smallest of the k largest }
import heapq def findKthLargest(nums, k): h = [] # the k largest, smallest on top for x in nums: heapq.heappush(h, x) if len(h) > k: heapq.heappop(h) # the smallest of k + 1 is not in the top k return h[0] # the smallest of the k largest
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.
Values arrive one at a time, and after each one, report the kth largest so far.
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.
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 } };
class KthLargest { private final PriorityQueue<Integer> h = new PriorityQueue<>(); // smallest on top private final int k; public KthLargest(int k, int[] nums) { this.k = k; for (int x : nums) add(x); } public int add(int val) { h.add(val); if (h.size() > k) h.poll(); return h.peek(); // the kth largest so far } }
import heapq class KthLargest: def __init__(self, k, nums): self.k, self.h = k, [] # the k largest, smallest on top for x in nums: self.add(x) def add(self, val): heapq.heappush(self.h, val) if len(self.h) > self.k: heapq.heappop(self.h) return self.h[0] # the kth largest so far
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.
The k points nearest the origin, in any order.
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.
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; }
public int[][] kClosest(int[][] points, int k) { PriorityQueue<int[]> h = new PriorityQueue<>((a, b) -> b[0] - a[0]); // the farthest on top for (int i = 0; i < points.length; i++) { int d = points[i][0] * points[i][0] + points[i][1] * points[i][1]; h.add(new int[]{d, i}); if (h.size() > k) h.poll(); // the farthest of k + 1 is out } int[][] out = new int[k][]; for (int j = 0; j < k; j++) out[j] = points[h.poll()[1]]; return out; }
import heapq def kClosest(points, k): h = [] # (−distance², index): the farthest on top for i, (x, y) in enumerate(points): heapq.heappush(h, (-(x * x + y * y), i)) if len(h) > k: heapq.heappop(h) # the farthest of k + 1 is out return [points[i] for _, i in h]
Taking the square root. It costs time and adds rounding error, and it never changes which point is nearer. Compare squared distances.
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.
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.
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.
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.
The k most frequent words, most frequent first, with equal counts in alphabetical order.
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.
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; }
public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> cnt = new HashMap<>(); for (String w : words) cnt.merge(w, 1, Integer::sum); PriorityQueue<String> h = new PriorityQueue<>((a, b) -> // the worst word on top cnt.get(a).equals(cnt.get(b)) ? b.compareTo(a) : cnt.get(a) - cnt.get(b)); for (String w : cnt.keySet()) { h.add(w); if (h.size() > k) h.poll(); // the worst of k + 1 leaves } LinkedList<String> out = new LinkedList<>(); while (!h.isEmpty()) out.addFirst(h.poll()); // the best first return out; }
import heapq from collections import Counter class Rank: # orders words worst first, for heapq def __init__(self, word, c): self.word, self.c = word, c def __lt__(self, other): # True when self ranks below other return self.c < other.c if self.c != other.c else self.word > other.word def topKFrequent(words, k): h = [] for w, c in Counter(words).items(): heapq.heappush(h, Rank(w, c)) if len(h) > k: heapq.heappop(h) # the worst of k + 1 leaves out = [] while h: out.append(heapq.heappop(h).word) return out[::-1] # the best first
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.
Fill an array by always splitting the longest run of zeros, taking the leftmost on a tie, at its middle.
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.
#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(""); } }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder sb = new StringBuilder(); while (t-- > 0) { int n = Integer.parseInt(in.readLine().trim()); int[] a = new int[n + 1]; PriorityQueue<int[]> h = new PriorityQueue<>((x, y) -> // longest, then leftmost x[0] != y[0] ? y[0] - x[0] : x[1] - y[1]); h.add(new int[]{n, 1}); // (length, left end) for (int i = 1; i <= n; i++) { int[] s = h.poll(); int l = s[1], r = l + s[0] - 1, m = (l + r) / 2; a[m] = i; if (m > l) h.add(new int[]{m - l, l}); if (r > m) h.add(new int[]{r - m, m + 1}); } for (int i = 1; i <= n; i++) sb.append(a[i]).append(' '); sb.append('\n'); } System.out.print(sb); } }
import sys, heapq def main(): data = sys.stdin.buffer.read().split() t, out = int(data[0]), [] for q in range(1, t + 1): n = int(data[q]) a = [0] * (n + 1) h = [(-n, 1)] # (−length, left end): longest, then leftmost for i in range(1, n + 1): neg, l = heapq.heappop(h) r = l - neg - 1 m = (l + r) // 2 # the left middle when the length is even a[m] = i if m > l: heapq.heappush(h, (-(m - l), l)) if r > m: heapq.heappush(h, (-(r - m), m + 1)) out.append(" ".join(map(str, a[1:]))) print("\n".join(out)) main()
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.
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.
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.
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.
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.
Rearrange the letters so that no two neighbours are equal, or return "" if that cannot be done.
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.
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; }
public String reorganizeString(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) cnt[c - 'a']++; PriorityQueue<int[]> h = new PriorityQueue<>((x, y) -> // the most left on top x[0] != y[0] ? y[0] - x[0] : x[1] - y[1]); for (int i = 0; i < 26; i++) if (cnt[i] > 0) h.add(new int[]{cnt[i], i}); StringBuilder out = new StringBuilder(); while (h.size() >= 2) { int[] a = h.poll(), b = h.poll(); // the most left, then a different letter out.append((char) ('a' + a[1])).append((char) ('a' + b[1])); if (--a[0] > 0) h.add(a); if (--b[0] > 0) h.add(b); } if (!h.isEmpty()) { if (h.peek()[0] > 1) return ""; // it would sit beside itself out.append((char) ('a' + h.peek()[1])); } return out.toString(); }
import heapq from collections import Counter def reorganizeString(s): h = [(-c, ch) for ch, c in Counter(s).items()] # (−count, letter): the most on top heapq.heapify(h) out = [] while len(h) >= 2: ca, a = heapq.heappop(h) # the most left cb, b = heapq.heappop(h) # a different letter out += [a, b] if ca + 1: heapq.heappush(h, (ca + 1, a)) if cb + 1: heapq.heappush(h, (cb + 1, b)) if h: if h[0][0] < -1: # two or more copies left would touch return "" out.append(h[0][1]) return "".join(out)
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.
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.
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.
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.
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.
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.
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; }
public int leastInterval(char[] tasks, int n) { int[] cnt = new int[26]; for (char t : tasks) cnt[t - 'A']++; PriorityQueue<Integer> h = new PriorityQueue<>(Collections.reverseOrder()); // the most on top for (int c : cnt) if (c > 0) h.add(c); ArrayDeque<int[]> wait = new ArrayDeque<>(); // (free at, runs left) int time = 0; while (!h.isEmpty() || !wait.isEmpty()) { time++; if (!wait.isEmpty() && wait.peekFirst()[0] == time) h.add(wait.pollFirst()[1]); // cooled down if (!h.isEmpty()) { int c = h.poll() - 1; // run the task with the most runs left if (c > 0) wait.addLast(new int[]{time + n + 1, c}); } // otherwise this unit is idle } return time; }
import heapq from collections import Counter, deque def leastInterval(tasks, n): h = [-c for c in Counter(tasks).values()] # runs left, negated: the most on top heapq.heapify(h) wait = deque() # (free at, runs left), in the order they ran time = 0 while h or wait: time += 1 if wait and wait[0][0] == time: heapq.heappush(h, -wait.popleft()[1]) # cooled down if h: c = -heapq.heappop(h) - 1 # run the task with the most runs left if c: wait.append((time + n + 1, c)) return time
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.
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.
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.
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.
Split the cards into groups of groupSize consecutive values, every card used once.
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.
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; }
public boolean isNStraightHand(int[] hand, int groupSize) { if (hand.length % groupSize != 0) return false; Map<Integer, Integer> cnt = new HashMap<>(); for (int x : hand) cnt.merge(x, 1, Integer::sum); PriorityQueue<Integer> h = new PriorityQueue<>(cnt.keySet()); // the smallest on top while (!h.isEmpty()) { int s = h.peek(); // nothing smaller is left: s starts a run for (int x = s; x < s + groupSize; x++) { int c = cnt.getOrDefault(x, 0); if (c == 0) return false; // a gap in the run cnt.put(x, c - 1); if (c == 1) { if (x != h.peek()) return false; // a smaller value would be stranded h.poll(); } } } return true; }
import heapq from collections import Counter def isNStraightHand(hand, groupSize): if len(hand) % groupSize: return False cnt = Counter(hand) h = list(cnt) # the distinct values heapq.heapify(h) # the smallest on top while h: s = h[0] # nothing smaller is left: s starts a run for x in range(s, s + groupSize): if cnt[x] == 0: return False # a gap in the run cnt[x] -= 1 if cnt[x] == 0: if x != h[0]: return False # a smaller value would be stranded heapq.heappop(h) return True
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.
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.
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.
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.
Numbers arrive one at a time, and at any moment report the median of all of them so far.
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.
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; } };
class MedianFinder { private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max on top private final PriorityQueue<Integer> hi = new PriorityQueue<>(); // min on top public void addNum(int num) { lo.add(num); hi.add(lo.poll()); // lo's maximum crosses over if (hi.size() > lo.size()) lo.add(hi.poll()); } public double findMedian() { if (lo.size() > hi.size()) return lo.peek(); return (lo.peek() + hi.peek()) / 2.0; } }
import heapq class MedianFinder: def __init__(self): self.lo = [] # the smaller half, negated: max on top self.hi = [] # the larger half, min on top def addNum(self, num): heapq.heappush(self.lo, -num) heapq.heappush(self.hi, -heapq.heappop(self.lo)) # lo's maximum crosses over if len(self.hi) > len(self.lo): heapq.heappush(self.lo, -heapq.heappop(self.hi)) def findMedian(self): if len(self.lo) > len(self.hi): return float(-self.lo[0]) return (-self.lo[0] + self.hi[0]) / 2
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.
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.
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.
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; }
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { PriorityQueue<int[]> locked = new PriorityQueue<>((a, b) -> a[0] - b[0]); // the cheapest on top PriorityQueue<Integer> ready = new PriorityQueue<>(Collections.reverseOrder()); // the largest profit on top for (int i = 0; i < profits.length; i++) locked.add(new int[]{capital[i], profits[i]}); while (k-- > 0) { while (!locked.isEmpty() && locked.peek()[0] <= w) ready.add(locked.poll()[1]); // now affordable if (ready.isEmpty()) break; // nothing affordable: w cannot grow w += ready.poll(); // the most profitable project } return w; }
import heapq def findMaximizedCapital(k, w, profits, capital): locked = list(zip(capital, profits)) # (capital needed, profit) heapq.heapify(locked) # the cheapest to start on top ready = [] # profits w can afford, negated: the largest on top for _ in range(k): while locked and locked[0][0] <= w: heapq.heappush(ready, -heapq.heappop(locked)[1]) # now affordable if not ready: break # nothing affordable: w cannot grow w -= heapq.heappop(ready) # the most profitable project return w
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.
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.
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.
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.
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.
k sorted lists. The narrowest range that holds at least one number from every list, the smaller start on a tie.
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.
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; }
public int[] smallestRange(List<List<Integer>> nums) { PriorityQueue<int[]> h = new PriorityQueue<>((a, b) -> a[0] - b[0]); // (value, list, index) int hi = Integer.MIN_VALUE; for (int i = 0; i < nums.size(); i++) { h.add(new int[]{nums.get(i).get(0), i, 0}); hi = Math.max(hi, nums.get(i).get(0)); } int[] best = {0, Integer.MAX_VALUE}; while (true) { int[] t = h.poll(); // the smallest head leaves if ((long) hi - t[0] < (long) best[1] - best[0]) best = new int[]{t[0], hi}; if (t[2] + 1 == nums.get(t[1]).size()) break; // its list ran out int v = nums.get(t[1]).get(t[2] + 1); h.add(new int[]{v, t[1], t[2] + 1}); hi = Math.max(hi, v); } return best; }
import heapq def smallestRange(nums): h = [(lst[0], i, 0) for i, lst in enumerate(nums)] # (value, list, index) heapq.heapify(h) # the smallest head on top hi = max(lst[0] for lst in nums) best = [h[0][0], hi] while True: v, i, j = heapq.heappop(h) # the smallest head leaves if hi - v < best[1] - best[0]: best = [v, hi] if j + 1 == len(nums[i]): return best # its list ran out nxt = nums[i][j + 1] heapq.heappush(h, (nxt, i, j + 1)) hi = max(hi, nxt)
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.
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.
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.
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.
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?
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.
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; }
public int furthestBuilding(int[] heights, int bricks, int ladders) { PriorityQueue<Integer> lad = new PriorityQueue<>(); // climbs on ladders, smallest on top for (int i = 0; i + 1 < heights.length; i++) { int d = heights[i + 1] - heights[i]; if (d <= 0) continue; // down or level: free lad.add(d); // a ladder, for now if (lad.size() > ladders) { // one too many: the smallest climb takes bricks bricks -= lad.poll(); if (bricks < 0) return i; } } return heights.length - 1; }
import heapq def furthestBuilding(heights, bricks, ladders): lad = [] # climbs on ladders, smallest on top for i in range(len(heights) - 1): d = heights[i + 1] - heights[i] if d <= 0: continue # down or level: free heapq.heappush(lad, d) # a ladder, for now if len(lad) > ladders: # one too many: the smallest climb takes bricks bricks -= heapq.heappop(lad) if bricks < 0: return i return len(heights) - 1
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.
Choose at most k songs to maximise (total length) × (smallest beauty among them).
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.
#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); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int k = (int) in.nval; long[] s = new long[n]; // beauty · 2^20 + length: one sortable key for (int i = 0; i < n; i++) { in.nextToken(); long t = (long) in.nval; in.nextToken(); long b = (long) in.nval; s[i] = (b << 20) | t; } Random rnd = new Random(); // shuffle, so no input is slow for quicksort for (int i = n - 1; i > 0; i--) { int j = rnd.nextInt(i + 1); long x = s[i]; s[i] = s[j]; s[j] = x; } Arrays.sort(s); PriorityQueue<Long> kept = new PriorityQueue<>(); // lengths, the shortest on top long sum = 0, best = 0; for (int i = n - 1; i >= 0; i--) { // the most beautiful first long t = s[i] & ((1 << 20) - 1), b = s[i] >> 20; kept.add(t); sum += t; if (kept.size() > k) sum -= kept.poll(); // drop the shortest best = Math.max(best, sum * b); // the smallest beauty so far } System.out.println(best); } }
import sys, heapq def main(): data = sys.stdin.buffer.read().split() n, k = int(data[0]), int(data[1]) songs = [(int(data[3 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)] # (beauty, length) songs.sort(reverse=True) # the most beautiful first kept, total, best = [], 0, 0 # lengths, the shortest on top for b, t in songs: heapq.heappush(kept, t) total += t if len(kept) > k: total -= heapq.heappop(kept) # drop the shortest best = max(best, total * b) # b is the smallest beauty so far print(best) main()
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.
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.
Ten moves, and each has a phrase in the statement that gives it away.
a heap: push and pop in O(log n), the top in O(1)
SIFT UP, SIFT DOWNO(log n)sink every parent, the last one first
HEAPIFYO(n)a heap of k with the worst kept on top
KEEP kO(n log k)every rule of the order goes in the comparison
KEY AND TIE-BREAKO(n log k)place the two letters with the most left each round
MOST LEFT FIRSTO(n log 26)a heap of free tasks, a queue of cooling ones
COOLDOWNO(m log 26)the smallest value left starts a run
SMALLEST STARTSO(n log n)two heaps whose tops meet in the middle
TWO HEAPSO(log n)one head per list; the smallest leaves
ONE HEAD PER LISTO(n log k)give it out freely, then trade the worst back
TAKE IT BACKO(n log L)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.
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.
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.
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.
None of these fail the samples. Each one fails a hidden test.
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.
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.
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.
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.
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.
Playlist's answer can pass 10¹⁷, and a sum of many values can pass 2³¹. Keep such sums and products in 64-bit integers.
Ten moves on one page. The right column is the cue for each.
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.
Module 19. Fifteen problems: twelve on LeetCode, two on Codeforces and one on GeeksforGeeks. Next in the sheet: tries.
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.