On this page
Description
A leaderboard keeps receiving scores, and after each one you're asked for the k-th best score so far. Re-sorting everything on each arrival costs O(n log n) per score; the history also grows without bound. Only the current top k can ever matter.
This skill keeps a size-k min-heap alive between calls, so each new value costs O(log k) and memory never grows past k. It also uses a heap as a live work queue that repeatedly combines the two smallest items, which is Huffman's algorithm behind the Connect Ropes problem.
We'll go from simple to more technical:
- The pattern: a min-heap of the k largest so far, kept as state across calls.
- A second flavor: a heap as a work queue that joins the two smallest and pushes the result back.
- Where it shows up (leaderboards, latency alerts, DEFLATE's Huffman codes).
- What breaks it: rebuilding per call, fewer than k values, sorting once, int totals.
The approach
Java
class KthLargest {
private final PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of the k largest so far
private final int k;
KthLargest(int k, int[] nums) {
this.k = k;
for (int x : nums) add(x); // the initial values go through the same path
}
int add(int val) {
heap.offer(val);
if (heap.size() > k) heap.poll(); // drop the weakest of the kept values
return heap.peek(); // the k-th largest so far
}
}
Python
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.heap = [] # min-heap of the k largest so far
self.k = k
for x in nums:
self.add(x) # the initial values go through the same path
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # drop the weakest of the kept values
return self.heap[0] # the k-th largest so far
It's the size-k min-heap from kth-element selection, kept alive between calls. Each add costs O(log k), memory stays O(k), and anything evicted can never matter again: k larger values are already kept. Before k values have arrived, the root is just the smallest value seen - the question guarantees answers are only needed once k values exist.
A second flavor: a heap as a live work queue
Some problems repeatedly take the smallest items, combine them, and put the result back - the heap is the queue of pending work. Joining ropes of lengths x and y costs x + y, and the joined rope can be joined again. Always join the two shortest:
Java
long connectRopes(int[] ropes) {
PriorityQueue<Long> heap = new PriorityQueue<>();
for (int r : ropes) heap.offer((long) r);
long cost = 0;
while (heap.size() > 1) {
long joined = heap.poll() + heap.poll();
cost += joined;
heap.offer(joined); // the new rope competes again
}
return cost;
}
Python
import heapq
def connect_ropes(ropes: list[int]) -> int:
heap = list(ropes)
heapq.heapify(heap)
cost = 0
while len(heap) > 1:
joined = heapq.heappop(heap) + heapq.heappop(heap)
cost += joined
heapq.heappush(heap, joined) # the new rope competes again
return cost
A rope's length is paid again in every later join it's part of, so short ropes should be joined first and long ones last - Huffman's algorithm. Sorting once and joining left to right isn't the same: for 1, 2, 3, 4, 5 it costs 34 instead of 33, because the running total stops competing with the remaining ropes. Four ropes of 10^9 already cost 8 * 10^9, past an int (Python's ints never overflow).
Where you'll see it
Leaderboards ("the score you need to reach the top 100") and alerting on the k-th highest latency in a stream keep a bounded heap alive between updates. Huffman's merge-the-smallest is how DEFLATE (zip, gzip, PNG) builds its prefix codes, and how optimal merge patterns combine sorted files.
Which tool for which job?
| You need | Use |
|---|---|
| The k-th largest after every add, fixed k | a size-k min-heap kept as state |
| Any rank after every add | an order-statistic tree, or a Fenwick tree over values |
| Repeatedly combine the two smallest | a min-heap work queue (Huffman) |
| The same, with the input already sorted | two FIFO queues, O(n) |
| Values that expire from a window | lazy deletion with live counts |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Rebuilding the heap on each call | O(n log n) per add | keep the heap as instance state |
| Reading the root before k values exist | it's the smallest so far, not the k-th largest | follow the problem's guarantee, or check the size |
| Sorting the ropes once | 1, 2, 3, 4, 5 costs 34 instead of 33 | push each joined rope back into the heap |
| int totals | four ropes of 10^9 overflow | accumulate in a long |
| Offer and poll on every add | about 17 comparisons per add for k = 100 | compare with the root first |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why can a value evicted from the size-k heap never become the k-th largest later?
Show answer
When it was evicted, k values at least as large were kept, and values only ever get added. It will always have at least k larger values ahead of it.
2. Why must joined ropes go back into the heap instead of sorting once?
Show answer
A joined rope is a new candidate that may be shorter than ropes still waiting. Sorting once and joining left to right keeps adding to one growing rope - 34 instead of 33 for 1, 2, 3, 4, 5.
3. What does add return before k values have been seen?
Show answer
The smallest value seen so far - the heap holds everything, fewer than k values. It only becomes the k-th largest once at least k values have arrived.
Key takeaways
- Keep the size-k min-heap as state; each add is O(log k) with O(k) memory.
- An evicted value can never re-enter the top k.
- A heap is also a live work queue: repeatedly join the two smallest (Huffman) and push the result back.
- Accumulate costs in a long.