Abstract:
Brodal recently introduced the first implementation of
imperative priority queues to support findMin, insert, and
meld in O(1) worst-case time, and deleteMin in 
worst-case time. These bounds are asymptotically optimal among all
comparison-based priority queues. In this paper, we adapt Brodal's data
structure to a purely functional setting. In doing so, we both simplify the
data structure and clarify its relationship to the binomial queues of
Vuillemin, which support all four operations in time.
Specifically, we derive our implementation from binomial queues in three
steps: first, we reduce the running time of insert to O(1) by
eliminating the possibility of cascading links; second, we reduce the running
time of findMin to O(1) by adding a global root to hold the minimum
element; and finally, we reduce the running time of meld to O(1) by
allowing priority queues to contain other priority queues. Each of these
steps is expressed using ML-style functors. The last transformation, known as
data-structural bootstrapping, is an interesting application of higher-order
functors and recursive structures.
Available as PostScript, PDF, DVI.