Two Whitepapers Every Developer Should Read

My go-to datastructure these days for priority queues is leftist heaps.

Short explanation of how they work: the core operation is the join, which joins two leftist heaps into one. A leftist heap is either empty or contains a head node with the highest priority element and two child heaps, a left and a right, and the height of the heap (the smallest distance between the root node and a leaf node). Joining two empty heaps results in the empty heap. Joining an empty heap and a non-empty heap simply results in the non-empty heap. Joining two non-empty heaps is the interesting case. I compare the highest priority nodes (root nodes) of the two heaps. The higher priority of the two becomes the new highest priority (root) node of the joined heap. This leaves me with three heaps- the heap containing the root node I didn’t promote, and the two child heaps of the root node I did promote. I pick the tallest of the three and make that the left child of the joined heap. I then recursively join the remaining two shorter heaps to make the right child.

To insert a node, I just create a one-node heap (both children are empty) and join it with the current heap. To remove the head node, I just replace the heap with the join of the two children of the root node.

Note that it’s easy to prove hard O(log N) worst case peformance, as you always go down the shortest branch. The algorithm oddly becomes more efficient if the heap becomes imbalanced. The best skip lists can give you is expected or media behavior, the random element prevents harder gaurentees. Leftist heaps are also easier to implement. And they’re easy to implement in a purely functional manner.

Why functional programming matters is a classic, though.