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)