Feedback request: priority queues in containers

Jim Apple jbapple+ghc-users at gmail.com
Tue Mar 16 12:45:57 EDT 2010


> 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


More information about the Glasgow-haskell-users mailing list