Is there an easy way to implement fast priority queue in Haskell?
I did a little googling and found an article on Finger Trees that can be used to implement a priority queue with the correct asymptotic complexity, but they are quite complex, but still the simplest thing I could find.
Is there a simple data structure that allows you to implement a fast priority queue in Haskell? Keep it simple as you can explain it to a novice programmer.
source to share
the heap package on Hackage claims to be based on Okasaki's left-handed heaps.
From the docs:
Choose MinHeap or MaxHeap if you want a simple min or max heap (which always keeps min / max element in the heap head).
If you want to manually annotate a priority value, e. d. IO () action using Int MinPrioHeap or MaxPrioHeap. They manage tuples (prio, val), so only the order (not the value) affects the order of the elements.
If you still need something different, define a custom order for the heap items by executing a HeapItem instance and letting the maintainer know what is missing.
source to share
The heap, which is the easiest to implement in Haskell, I know is Heap Conjugation .
It supports constant time insertion and concatenation (amortized) and logarithmic time for deleting items.
data Heap a = Empty | Heap a [(Heap a)]
deriving Show
findMin :: Heap a -> a
findMin (Heap h _) = h
merge :: Ord a => Heap a -> Heap a -> Heap a
merge Empty h = h
merge h Empty = h
merge h1@(Heap x hs1) h2@(Heap y hs2)
| x < y = Heap x (h2:hs1)
| otherwise = Heap y (h1:hs2)
mergePairs :: Ord a => [Heap a] -> Heap a
mergePairs [] = Empty
mergePairs [h] = h
mergePairs (h1:h2:hs) = merge (merge h1 h2) (mergePairs hs)
insert :: Ord a => a -> Heap a -> Heap a
insert x = merge (Heap x [])
deleteMin :: Ord a => Heap a -> Heap a
deleteMin (Heap x hs) = mergePairs hs
source to share