DSA · interactive
Heap: top k of a stream
To keep the k largest numbers, hold them in a min-heap. The smallest of the winners sits at the root, so each new number needs one comparison to be rejected, or log k swaps to get in.
Stream
- 5
- 1
- 9
- 3
- 7
- 2
- 8
- 6
- 4
Min-heap (size 3)
array: [] · root = smallest of the top 3
Keep a min-heap of the 3 largest so far. Its root is the smallest of them: the one to beat.
k
1 Children of index i live at 2i+1 and 2i+2. Every parent is smaller than its children, so the minimum is always at index 0.
parent(i) = (i - 1) >> 1
2 3 4
Now solve it
Heap / Priority Queue: 5 problems
See all →In production
Tools and technologies
Heaps back every priority queue.
Not tied to one language — use these names when you search docs or design a system.