Data structures and patterns · Question 41 of 50
What is a heap? How do you find the top K items?
Priority queues and their cost.
The answer
A heap is a complete binary tree stored in an array, where each parent is smaller than its children (a min-heap) or larger (a max-heap). The top is always the minimum (or maximum), readable in O(1); adding an item and removing the top take O(log n). It powers priority queues: schedulers, Dijkstra, merging sorted lists.
For the K largest of n items, keep a min-heap of size K: add each item, and when the heap grows past K, remove the smallest. You end with the K largest in O(n log K), better than sorting everything when K is small.
The picture
min-heap of size 3, items: 5 1 9 3 7 [5] → [1 5] → [1 5 9] → add 3, drop 1 → [3 5 9] → add 7, drop 3 → [5 7 9] the top 3 = 5, 7, 9
The median of a stream of numbers?
Show the answer
Two heaps: a max-heap for the lower half and a min-heap for the upper half, kept balanced; the median sits at their tops.