Heaps and priority queues

In June 1964 Communications of the ACM printed "Algorithm 232: Heapsort" by J. W. J. Williams. Alongside a new sorting method it introduced the data structure it relied on, the binary heap: a tree that lives inside an ordinary array, where the parent of position i is found by arithmetic rather than by following a pointer.

Later that year Robert Floyd showed how to arrange an arbitrary array into a heap in linear time. Six decades on, every operating-system scheduler, network simulator and shortest-path algorithm that needs "the most urgent item next" uses the same idea.