On 6/20/07, Spencer Janssen
(I often miss priority queues)
I must say, there have been several times lately where I have wanted such a type. Actually, I've found Data.Map isn't too bad if you use deleteMin/deleteMax. What's more, deleteM{in,ax} & insert are both O(log n) for most reasonable implementations that could be used for a Data.Map-like structure, which works out much the same in many cases. In particular, I find my self wanting to use a priority queue for N-way sorted merge, which you can do with Data.Map: (compiles, so clearly works even though I have not tested it. ;-) ) import Data.List as List import Data.Map as Map merge :: Ord t => [[t]] -> [t] merge lists = merge' $ Map.fromList $ concatMap makePair lists where makePair [] = [] makePair (x:xs) = [(x,xs)] merge' heap | Map.null heap = [] | otherwise = x:(merge' $ removeEqual x $ reinsert xs heap') where ((x,xs), heap') = deleteFindMin heap reinsert [] heap = heap reinsert (x:xs) heap = Map.insert x xs heap removeEqual x heap | Map.null heap = heap | x /= y = heap | otherwise = removeEqual x $ reinsert ys heap' where ((y,ys), heap') = deleteFindMin heap The other thing I have found myself doing often is using splitLookup followed by union, though what I really want is "join" being the dual of split - i.e. requiring all the keys in the rhs to be greater than the keys in the lhs. My own AVL tree implementation has this operation which is O(log n), which is rather better than union's O(n log n). T. -- Dr Thomas Conway drtomc@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.