Today’s Programming Praxis problem is about priority queues. Specifically, we have to implement one using a Leftist Heap.
We define a priority queue as follows. It’s basically a binary tree, but with an extra field in which we store the rank.
data PQueue a = Node Int a (PQueue a) (PQueue a) | Empty
Empty nodes have rank 0.
rank :: PQueue a -> Int rank Empty = 0 rank (Node r _ _ _) = r
A convenience function for node creation that calculates the rank automatically:
node :: a -> PQueue a -> PQueue a -> PQueue a node i l r = if rank l > rank r then node i r l else Node (1 + rank r) i l r
Two priority queues can be merged as follows:
merge :: (a -> a -> Bool) -> PQueue a -> PQueue a -> PQueue a merge _ Empty q = q merge _ q Empty = q merge p l@(Node _ il _ _) r@(Node _ ir lc rc) = if p ir il then node ir lc (merge p l rc) else merge p r l
To insert an item into a priority queue we make a new queue out of it and merge it into our original queue.
insert :: (a -> a -> Bool) -> a -> PQueue a -> PQueue a insert p i = merge p (node i Empty Empty)
We convert a list to a priority queue by inserting all the items into an empty queue.
fromList :: (a -> a -> Bool) -> [a] -> PQueue a fromList p = foldr (insert p) Empty
And to do the opposite we keep taking the root of the queue and merging its branches.
toList :: (a -> a -> Bool) -> PQueue a -> [a] toList _ Empty = [] toList p (Node _ i l r) = i : toList p (merge p l r)
With these functions, we can easily sort a list on priority by converting it to a priority queue and back.
pqSort :: (a -> a -> Bool) -> [a] -> [a] pqSort p = toList p . fromList p
And finally we test if everything works ok.
main :: IO () main = print $ pqSort (<) [3, 7, 8, 1, 2, 9, 6, 4, 5]
30 lines counting white space. Not bad.
Tags: heap, kata, leftist, praxis, priority, programming, queue
Leave a comment