[Haskell-cafe] Performance of functional priority queues

Louis Wasserman wasserman.louis at gmail.com
Fri Dec 25 14:59:39 EST 2009


>> One of the correspondents in that thread claims that it is
>> provably impossible to have an efficient priority queue implementation
>> without mutability.  I think he's cuckoo.  But I'd like to have some
>> numbers to back me up.

He is cuckoo, and here's proof:
http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf

<http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf>This demonstrates a
functional priority queue that performs every desired operation in
asymptotically optimal time.  Granting that its constant factor could be
significantly improved, realize that there are more complicated functional
data structures with similar asymptotic guarantees.  (Observation: I'm
pretty sure that the Fibonacci heap is actually surprisingly functional.)

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091225/fdf103e9/attachment.html


More information about the Haskell-Cafe mailing list