Binary Heap

If a system constantly needs the current minimum or maximum, scanning an array or list each time is too expensive, and maintaining full sorted order on every update can also be more work than necessary. A heap solves that pressure by preserving only the ordering needed to guarantee the root element.

Schedulers, graph algorithms, simulation engines, and external sorting workloads have long needed the same primitive: repeatedly choose the next best candidate. That requirement drove the development of heaps, priority queues, and heapsort. Their importance comes from turning priority selection into a reusable systems-level tool rather than an ad hoc scanning step.

Because a heap is a complete binary tree, it can be stored compactly in an array. Parent and child positions are derived by index arithmetic rather than by explicit pointers. On insertion, the new value is appended at the end and moved upward through sift up until the heap property is restored. On removal of the root, the last value is moved to the top and pushed downward through sift down. Those restoration steps are the core of heap maintenance.

A heap and a BST answer different questions. A heap is for 'what is the single most urgent item right now?' A BST is for 'where does this value sit in sorted order, and what values are before or after it?' Heaps also sit on top of arrays internally, but they are not designed for fast arbitrary indexing the way arrays are.

Heaps appear in job schedulers, timer queues, Dijkstra and A* frontiers, top-k streaming problems, and k-way merge routines where the next best candidate must be chosen repeatedly. They are strongest when priority selection dominates the workload. The more the workload cares about ordered iteration or range queries instead of repeated root extraction, the less natural a heap becomes.