Feedback request: priority queues in containers

Jim Apple jbapple+ghc-users at
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

More information about the Glasgow-haskell-users mailing list