> Specifically, we use a binomial heap, which offers > > O(log n) worst-case union > O(log n) worst-case extract (this in particular was a key objective of ours) > amortized O(1), worst-case O(log n) insertion. (In a persistent context, > the amortized performance bound does not necessarily hold.)
Why not use Okasaki & Brodal's "Optimal Purely Functional Priority Queues"? They offer worst case: * O(1) union, findMin, and insert * O(lg n) deleteMin http://www.eecs.usma.edu/webs/people/okasaki/jfp96/index.html ftp://ftp.daimi.au.dk/pub/BRICS/Reports/RS/96/37/BRICS-RS-96-37.pdf _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
