Progress on priority queues for containers

Milan Straka fox at
Mon Mar 8 14:28:05 EST 2010


I have uploaded a small benchmark to the ticket.

> 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. 

I think PQueue in containers should work in a persistent setting, which
pairing heaps do not. That is why I put lazy pairing heaps in the
benchmark. This variant is from Okasaki's book Purely Functional Data
Structures and is _conjectured_ (and believed, at least by Okasaki and
me :) to have same amortized bounds in persistent setting.

Personally I would put lazy pairing heaps to the containers (beware, the
current implementation has to be yet worked if we agree). If not,
I would use binomial heaps or maybe benchmark leftist heaps.

Have a nice day,

More information about the Libraries mailing list