#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:18 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.
Yes, I think that the O(N) delete-min in persistent setting is a show-
stopper.
If amortized bounds are enouth, maybe lazy pairing heaps? They seem to
even beat pairing heaps in the "input is not uniform" case.
If we want real-time bounds, binomial heaps are probably fine. Do you have
any idea how a leftist heap would do? We can perhaps add it to the
benchmark...
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:19>
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
