Optimal Purely Functional Priority Queues
📜 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 O(log n) 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 O(log n) 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.
✨ Summary
The paper develops a persistent, purely functional priority queue with worst-case bounds of O(1) for findMin, insert, and meld, and O(log n) for deleteMin. It derives the structure incrementally from ordinary binomial queues:
- Skew binomial queues replace ordinary binary-rank behavior with skew-binary behavior, ensuring that insertion performs at most one link rather than a cascade of links.
- A global root stores the minimum element explicitly, reducing
findMinto constant time. - Data-structural bootstrapping represents a priority queue as a primitive priority queue containing recursively structured priority queues. This reduces
meldto insertion into the underlying structure while preserving persistence.
The implementation is expressed using Standard ML functors. The paper also discusses representation optimizations, the effect of lazy evaluation on worst-case versus amortized bounds, and the difficulty of supporting operations such as decreaseKey and arbitrary deletion in a purely functional setting. The resulting bounds are presented as asymptotically optimal for comparison-based priority queues. (resolve.cambridge.org)
The work influenced subsequent functional-data-structure research and implementations. Its bootstrapped skew-binomial design was implemented in Haskell-oriented libraries; for example, the Scalaz Heap documentation explicitly identifies its implementation as based on the paper. A Haskell community report also documents a Coq-verified implementation of the paper’s priority queues, distributed as the meldable-heap package. (scalaz.github.io) Bibliographic services record later citations in research on skew-binary numeral systems, heaps, verification, and functional programming, indicating continued use of the paper as a reference for persistent meldable priority queues. (cambridge.org)