#3909: Priority queues in containers
-------------------------------------------+--------------------------------
Reporter: LouisWasserman | Owner: LouisWasserman
Type: feature request | Status: assigned
Priority: normal | Milestone:
Component: libraries (other) | Version: 6.12.1
Keywords: containers, priority queue | Difficulty:
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: None/Unknown
-------------------------------------------+--------------------------------
Comment(by LouisWasserman):
Hmmmkay.
I'm going to make my own vote for {{{Maybe (a, PQueue a)}}}, and change
it, since we appear to be in charge...
After doing my own experiments with lazy pairing heaps, I'm still not sure
I'm willing to support lazy pairing heaps, again out of concern for the
real-time-performance crowd. The distinction is really the following:
Binomial queues support amortized O(1) insertion, but worst-case O(log n).
Pairing heaps support amortized O(log n) delete-min, but worst-case O(n).
Okasaki doesn't debate worst-case performance.
I'm convinced that this approach doesn't risk O(n^2) performance in a
persistent context, now, which is a significant improvement, but I'm not
fully convinced it's enough yet.
Uploading my updated versions now.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:24>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
