Heap Patterns

Heap patterns keep a small heap of the items that are still in contention, so each new item is compared with the one at the top instead of with everything seen so far. It matters because questions about the k largest, the next smallest of several sources or the middle of a growing list otherwise sort everything, or hold everything, when only a few values can be in the answer. The topic opens on a min-heap of three that keeps the three largest values, keeps the three loudest readings of a day without sorting the day, and gives the top-k template in Python, Java and TypeScript. It merges sorted lists by holding one item from each, tracks the middle waiting time in a clinic with two heaps, shows why a max-heap keeps the wrong k, and ends with an exercise on the campsites nearest a trailhead.