Leftist Trees

I coded this log-n version of a priority queue in Smalltalk working from the pseudo-code in Knuth volume III. wikipedia

The algorithm insures that the highest priority node is at the root of the tree and that the next highest priority is at the root of either the left or right subtree.

The algorithm maintains logarithmic behavior by balancing the tree after each insert or remove. Balancing involves a pointer swapping "rotate" which might precipitate further rotates down one branch or the other.

The Smalltalk version appeared even simpler than Knuth's pseudo-code because some case analysis was pushed onto method dispatch through the use of Null Objects.

A discrete event simulator would use a priority queue for its event list. See Radio Network Simulator.

See also Systolic Stack.