[Haskell-cafe] Priority Queue?

Ross Paterson ross at soi.city.ac.uk
Sun Nov 26 20:36:45 EST 2006


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)



More information about the Haskell-Cafe mailing list