#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):
Sounds good. I'm uploading a quickie implementation of skew heaps, which
Wikipedia says should beat leftist heaps, but which is beaten by my
binomial heaps.
I'd be interested to help with the proof that lazy pairing heaps are
amortized O(log n), and I certainly believe the claim, but I'm still
inclined to use binomial heaps in containers, and then the two of us
should co-release a lazy pairing heap implementation that we recommend in
the containers documentation.
Look forward to seeing your results.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:30>
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
