21. Heaps & Priority Queue

A heap always gives you the smallest (min-heap) or largest (max-heap) item in O(1), and adding or removing costs O(log n). In Java it's PriorityQueue, which is a min-heap by default; use Collections.reverseOrder() or a comparator for a max-heap.

Three patterns cover most questions. For Top K, keep a heap of size k, and the top is your boundary. For a K-way merge, put the head of each list in a heap and always take the smallest. For a running median, use two heaps that each hold half of the numbers.