Priority queues

Array-backed binary heaps rely on overwriting slots, so functional heaps are trees, and their key operation is merge: insert merges in a one-element heap, and delete-min merges the root’s children. Okasaki’s book presents leftist heaps first, as simple in either setting. Binomial heaps mirror binary numbers, one tree per 1 bit; Okasaki’s skew binomial heaps make insert O(1) in the worst case. Brodal and Okasaki (1996) went all the way: findMin, insert and meld in O(1) and deleteMin in O(log n), all worst case, derived from binomial queues in three steps (no cascading links, a global root for the minimum, and heaps that contain heaps).

Simpler options trade guarantees for code you can write from memory. Pairing heaps (Fredman, Sedgewick, Sleator and Tarjan, 1986) are a root plus a list of sub-heaps, with O(1) find-min, meld and insert and O(log n) amortized delete-min. Okasaki’s maxiphobic heaps (2005), proposed for teaching, compare subtree sizes instead: when merging, the two smaller of the three leftover subtrees are merged first, so each step works on at most two thirds of the elements and merge stays O(log n).

A priority search queue (Hinze, 2001) is both a map and a priority queue: find the binding for a key in O(log n) and read the binding with the smallest priority in O(1). Hinze uses it for a simple, purely functional version of Dijkstra’s shortest-path algorithm.