Optimal Purely Functional Priority Queues

Companion source code to

Gerth Stølting Brodal and Chris Okasaki
Optimal Purely Functional Priority Queues
Journal of Functional Programming, 6(6):839-857, November 1996.

All companion source code is written for SML/NJ (version 0.93).

priq.sig: signature for priority queues
binomial.sml: implementation of binomial queues (all operations take O(log n) time)
skewbinomial.sml: implementation of skew binomial queues (reduces insert to O(1) time)
addroot.sml: a functor to add a global root (reduces findMin to O(1) time)
bootstrap.sml: a functor to bootstrap priority queues (reduces meld to O(1) time). NB: this functor will not compile under existing SML compilers because it requires recursive structures.
final.sml: final implementation of bootstrapped skew binomial queues (findMin, insert, and meld take O(1) time; deleteMin takes O(log n) time)