Intro

What if you need to repeatedly find and remove the smallest element from a collection? An unsorted array gives $O(n)$ per removal.

Keep the array sorted in reverse and the minimum sits at the end: $O(1)$ removal, but $O(n)$ insertion. Heaps balance both: $O(\log n)$ insertion and removal, $O(1)$ peek at the minimum.

In this section, you'll learn heaps, then learn patterns like $k$-th element finding, merging sorted lists, and the two-heaps technique for running medians.