Heap (Priority Queue)

A heap is a way of organizing items so you can always grab the “most important” one quickly. Imagine a hospital triage list: patients have priorities, and you repeatedly need the highest-priority patient next—not necessarily the entire list perfectly sorted, just the next most urgent. A heap is typically a binary tree (often stored compactly in an array) with a simple rule called the heap property: - Max-heap: every parent node’s key is ≥ each of its children (so the maximum item sits at the root). - Min-heap: every parent node’s key is ≤ each of its children (so the minimum item sits at the root). That one rule is the “secret”: by enforcing a local order (parent vs. children), you get a global guarantee that the best item is always at the top. Then operations become efficient: - peek (see best item): O(1) because it’s at the root - insert: O(log n) by “bubbling up” to restore the heap property - extract-max/min (remove best item): O(log n) by moving the last item to the root and “sifting down” In practice, heaps power priority queues: data structures where each item has a priority and you repeatedly remove the highest (or lowest) priority item first.

Heaps rose to prominence in the early 1960s alongside the growing need to manage large collections of data efficiently on limited hardware. The key insight was that full sorting is often unnecessary: many real problems only need repeated access to the next best element. This idea became especially influential through Heapsort (1964), which showed how the heap property could be maintained efficiently to sort in-place using an array. Soon after, Robert Floyd demonstrated a faster method to build a heap from an array (the classic “heapify” improvement), helping cement heaps as a foundational tool in algorithms and systems—particularly for scheduling and graph algorithms where priorities constantly change.

Pioneered by: The heap data structure is most closely associated with J. W. J. Williams (1964), who introduced it in the context of Heapsort. Robert W. Floyd (1964) is credited with an important improvement: the efficient bottom-up heap construction (heapify).

• Task scheduling in operating systems (e.g., always run the highest-priority process next)
• Shortest-path routing and navigation (e.g., Dijkstra’s and A* algorithms use priority queues)
• Event simulation systems (e.g., discrete-event simulators always process the next event by earliest time)
• Streaming/online analytics (e.g., keeping top-k largest items seen so far)
• Data compression (e.g., Huffman coding repeatedly combines lowest-frequency symbols using a min-heap)