#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