Data structures and patterns · Question 41 of 50

What is a heap? How do you find the top K items?

What they're checking

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 follow-up they'll ask

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.

Your progress stays on this device.