pattern heroPT–23LeetCode Extension

Heap and top K

A heap always keeps the smallest (or the biggest) item on top and updates quickly when something is added or taken. So to get the best k you do not have to sort everything.

Variant
P09 Heap and top Kk largest · 1×

Example problem: find the 3 largest numbers in [4, 1, 7, 3, 8, 2, 9].

4173829min-heapk = 3
not read yetcurrent number xin the heaproot, compared with xdroppedanswer

Start with an empty min-heap

heap = []x = –
01/29
restart · back · play · step
Speed
1function kLargest(nums, k):
2 heap = empty min-heap
3 for each x in nums:
4 if size of heap < k:
5 push x into heap
6 else if x > min of heap:
7 pop min from heap
8 push x into heap
9 return heap

← → step · space play/pause

How to recognise

the k largest, smallest, closest or most frequent items, or the k-th one, often from a long list or a stream.

How to solve problems like this

  1. Flip the heap: a min-heap for the k largest, a max-heap for the k smallest.
  2. Pick the key to compare: the value, a count from a hash map, the distance to a point.
  3. Fill the heap up to k items. After that, a new item replaces the root only if it beats it.
  4. At the end the heap holds the answer, and its root is the k-th best.

Variant: Merge k lists

The same, but the heap holds the first item of each of k sorted lists. The next item of the merged answer is always on top, so the k lists are not compared every time.

  1. Put one candidate per list in the heap: its first node, skipping empty lists. The heap compares nodes by node.val.
  2. Pop the smallest node and append it to the result.
  3. If the popped node has a next, push node.next: it becomes that list's candidate.
  4. The same shape finds the k-th smallest in a matrix with sorted rows (pop k times) and the smallest range that covers every list (also track the largest candidate).

Variant: Two heaps

The same, but with two heaps: one holds the smaller half of the numbers, the other the bigger half. The median is always on top of one of them, so nothing is re-sorted after each new number.

  1. Spot it: numbers arrive over time and you keep needing the middle, or any split into a lower and an upper part.
  2. Keep two heaps: a max-heap low for the smaller half and a min-heap high for the larger half.
  3. Add each number to low, then move the top of low to high. This keeps every value in low below every value in high.
  4. If high grew bigger than low, move its top back. Now low has the same size or one more.
  5. Read the answer from the tops: the top of low for an odd count, the average of both tops for an even one.

Where it's used

  • Timers in Node.js. libuv, the library under Node.js, keeps timers in a heap: the one due first is always on top. So it never has to look through every timer to know how long to wait.
  • Python. heapq.nlargest(k, data) keeps a heap of the best k and runs the rest of the data past it instead of sorting everything.
  • RocksDB. RocksDB stores data in several sorted files. To read them in order, it merges them through a heap that always has the next key on top.