Couldn't Data.Sequence be augmented with the PSQ operations?
On Wed, Dec 24, 2008 at 1:40 PM, Ross Paterson <r...@soi.city.ac.uk> wrote: > On Wed, Dec 24, 2008 at 12:23:47PM +0000, Johannes Waldmann wrote: >> Hello. I am looking for a single-source shortest-path implementation >> (Dijkstra's algorithm, cf. Chapter 25 in Cormen,Leiserson,Rivest). >> An efficient implementation would use Binomial or Fibonacci heaps >> (Chap.s 20 + 21). The problem seems to be "(fib-)heap-decrease-key" >> which assumes that we have, with the key, a pointer to its position >> in the heap, because that is where there will be a destructive update. >> How is this dealt with in Okasaki's book + library? - Thanks, J.W. > > The structure you're describing is a priority search queue. They're not > covered in Okasaki's book, but Ralf Hinze gave an implementation in ICFP > 2001, which Scott Dillard has placed on hackage as PSQueue. They can > also be implemented using finger trees. > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe