Re: [Haskell-cafe] Priority Queue?
"Ken Takusagawa" <[EMAIL PROTECTED]> writes: > Is there a Haskell implementation of an efficient priority queue > (probably heap-based) out there that I can use? I do not see it in > the GHC libraries. ISTR Okasaki's algorithms book has a suitable one. -- Mark ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Priority Queue?
On Sun, Nov 26, 2006 at 04:58:13PM -0500, Ken Takusagawa wrote: > Is there a Haskell implementation of an efficient priority queue > (probably heap-based) out there that I can use? I do not see it in > the GHC libraries. As already mentioned, there are several in Edison. If you want to roll your own, you can't get much simpler than Okasaki's lazy skew heaps, from "The Fun of Programming" (the Edison version is a specialized version of this): data Tree a = Null | Fork a (Tree a) (Tree a) isEmpty :: Tree a -> Bool isEmpty Null = True isEmpty _ = False minElem :: Tree a -> a minElem (Fork x a b) = x deleteMin :: Ord a => Tree a -> Tree a deleteMin (Fork x a b) = merge a b insert :: Ord a => a -> Tree a -> Tree a insert x a = merge (singleton x) a where singleton x = Fork x Null Null merge :: Ord a => Tree a -> Tree a -> Tree a merge a Null = a merge Null b = b merge a b | minElem a <= minElem b = join a b | otherwise = join b a where join (Fork x a b) c = Fork x b (merge a c) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Priority Queue?
I recommend the Edison library, which has several heap implementations. http://www.eecs.tufts.edu/~rdocki01/edison.html Cheers, Spencer Janssen On Nov 26, 2006, at 3:58 PM, Ken Takusagawa wrote: Is there a Haskell implementation of an efficient priority queue (probably heap-based) out there that I can use? I do not see it in the GHC libraries. ___ 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
Re: [Haskell-cafe] Priority queue
On 12/15/05, Joel Reymont <[EMAIL PROTECTED]> wrote: > Does anyone have priority queue Haskell code that they would be > willing to share or point me to? > > Thanks, Joel > Here's one I wrote some time ago: http://www.dtek.chalmers.se/~sylvan/PriorityQueue/ It's implemented as skewed binomial trees. The oeprations insert, findMin and meld are all O(1), deleteMin is O(log n). That's optimal (well, the theoretical optimum is that all operations are O(1) except one which is O(log n), it could theoretically be some other function that's O(log n), but for this implementation it's deleteMin). In practice, for fewer elements, it may be faster to use other structures though (like lazy pairing heaps). The constant term is kinda high (though not *that* bad). /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Priority queue
I would appreciate it, thank you Ben! Is this the paper? http://www.informatik.uni-bonn.de/ ~ralf/publications/UU-CS-2001-09.pdf On Dec 15, 2005, at 12:26 PM, Benjamin Franksen wrote: I can send you the sources (today, evening, can't access it at work). -- http://wagerlabs.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Priority queue
On Thursday 15 December 2005 11:50, Joel Reymont wrote: > Does anyone have priority queue Haskell code that they would be > willing to share or point me to? In fact I have one. It is based on 2-3 finger trees as described in a paper by Ralf Hinze. it is even better because it is a ordered sequence data type, rather than just a priority queue: all operations are constant time at both ends (max resp.min end). It is also quite memory efficient (last time I checked, it used about half the memory compared to data.Set). I can send you the sources (today, evening, can't access it at work). Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
