#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:24 LouisWasserman]:
> Hmmmkay.
>
> I'm going to make my own vote for {{{Maybe (a, PQueue a)}}}, and change
it, since we appear to be in charge...
Great :)
>
> After doing my own experiments with lazy pairing heaps, I'm still not
sure I'm willing to support lazy pairing heaps, again out of concern for
the real-time-performance crowd. The distinction is really the following:
>
> Binomial queues support amortized O(1) insertion, but worst-case O(log
n).
> Pairing heaps support amortized O(log n) delete-min, but worst-case
O(n). Okasaki doesn't debate worst-case performance.
The lazy pairing heaps are really only amortized -- you know (if the
conjecture is right) that I inserts, M merges and D delete-mins take O(I +
D log N), but a delete-min can take up to O(N) time (which cannot happen
frequently, of course).
If we want structure with worst-case bounds, it is not (any kind of)
pairing heaps.
For me, a quicker structure with amortized bounds is better in Haskell. If
you for example perform a heap-sort, than the amortized bounds works well
and you have O(N log N) guaranteed complexity. Only thing that doesn't
work is "now immediately perform this delete-min in O(log N)". But this
kind of operations are not common in Haskell -- you would have to
carefully evaluate every operation, because trivially performing 'insert'
would probably create only a thunk which the first delete-min would have
to evaluate and thus could take O(N).
But, as you said, binomial heaps are worst-case. They have provable
bounds. And are a common knowledge -- which this variant of lazy pairing
heap is not.
How is it with stability -- don't you know?
Milan
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:26>
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
