Is there a simple way to implement a fast priority queue in Haskell?

Question

I've googled a bit and found a paper on Finger Trees, which can be used to implement a priority queue with proper asymptotic complexity, but they're quite complicated, but still about the simplest thing I could find.

Is there a simple data structure that allows to implement a fast priority queue in Haskell? Think simple as in you could explain it to a novice programmer.

Answer 1

The heap package on Hackage claims to be based on Okasaki's leftist heaps.

From the docs:

Choose MinHeap or MaxHeap if you need a simple minimum or maximum heap (which always keeps the minimum/maximum element at the head of the Heap).

If you wish to manually annotate a value with a priority, e. g. an IO () action with an Int use MinPrioHeap or MaxPrioHeap. They manage (prio, val) tuples so that only the priority (and not the value) influences the order of elements.

If you still need something different, define a custom order for the heap elements by implementing an instance of HeapItem and let the maintainer know what's missing.

Answer 2

The heap that is the simplest to implement in Haskell I know is the Pairing Heap.

It supports insert and merge in constant time (amortised) and logarithmic time to delete elements.

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