#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 milan):
Replying to [comment:15 LouisWasserman]:
> What do people think of the following?
>
> Put pairing heaps (by far the fastest implementation so far, nearly 2.3x
faster than binomial heaps) into containers. Launch packages containing
high-quality priority search queues and real-time-ish binomial queues.
(The binomial queue implementation guarantees that deleteMin has worst-
case time O(log n), while pairing heaps have worst-case O(n). For people
with real-time speed needs, this is relevant.) Endorse these packages in
the documentation in Data.PQueue, for people with these specialized needs.
I think PQueue in containers should work in a persistent setting, which
pairing heaps do not. That is why I put lazy pairing heaps in the
benchmark. This variant is from Okasaki's book Purely Functional Data
Structures and is _conjectured_ (and believed, at least by Okasaki and
me:) to have same amortized bounds in persistent setting.
Personally I would put lazy pairing heaps to the containers (beware, the
current implementation has to be yet worked if we agree). If not, I would
use binomial heaps or maybe benchmark leftist heaps.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:17>
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
