#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.
I'm starting to feel, though, that I can't justify putting pairing heaps
in containers, because of the possibility that even under normal usage
that O(n^2) work could be done when O(n log n) was expected. The worst
case for delete-min of a pairing heap is O(n), and if that operation is
performed several times in that worst case, it'd get ugly. It makes me
sad, because like your benchmark shows, pairing heaps are so effective in
the single-threaded case. For the same reason, I'd prefer a strict data
structure, because we have to have an implementation that's suitable for
*everybody,* including the people with serious real-time speed
requirements.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:18>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
