Functional Binomial Queues

Efficient implementations of priority queues can often be clumsy beasts. We express a functional implementation of binomial queues which is both elegant and efficient. We also quantify some of the differences with other functional implementations. The operations decreaseKey and delete always pose a problem without destructive update, we show how our implementation may be extended to express these. 1 Functional priority queues A crucial part of many algorithms is the data structure that is used. Frequently, an algorithm needs an abstract data type providing a number of primitive operations on a data structure. A priority queue is one such data structure that is used by a number of algorithms. Applications include, Dijkstra's [4] algorithm for single-source shortest paths, and the minimum cost spanning tree problem (see Tarjan [12] for a discussion of minimumspanning tree algorithms). See Knuth [8] and Aho et al [1] for many other applications of priority queues. A priority queue is a ..