Optimal Purely Functional Priority Queues

Abstract

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.