#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):
Interesting.
Again, I don't think most people need the full power of priority search
queues, and I'm inclined to suggest that we just create a package for
those, and then maybe link to it from the containers documentation.
(Also, after painstakingly editing the implementation to support general
ordered values, it was slower than the binomial queue implementation.)
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:15>
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
