Couldn't Data.Sequence be augmented with the PSQ operations?
On Wed, Dec 24, 2008 at 1:40 PM, Ross Paterson
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