[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