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.

Yes. Buy a copy of *Purely Functional Data Structures* by Chris Okasaki. The leftist heaps he describes are quite simple. He also describes a variety of other priority queue implementations, all the way up to Brodal-Okasaki queues (priority queues with O(1) merge). Finger trees are kind of silly for priority queues, unless you want easy access to both the maximum and the minimum. — dfeuer, Nov 25 '14 at 21:23
Could someone explain why this was getting downvoted? I thought you were supposed to write a comment explaining why you downvoted something if a comment providing that reason didn't already exist. — bitemyapp, Nov 25 '14 at 21:41
[This SO question](http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-implementations-in-haskell) contains an extensive discussion on Haskell pqueue implementations. — ErikR, Nov 25 '14 at 22:24
@bitemyapp, if you hover your mouse over the "downvote" button, it will tell you. I personally downvoted it because, despite the OP's claim to the contrary, it seems clear that they put virtually no effort into finding an answer. The first two pages of Google search results for `Haskell priority queue` turn up a wealth of information. I don't see leftist heaps there, but I do see binomial heaps, which aren't too complicated either. — dfeuer, Nov 25 '14 at 23:13
@dfeuer Well first of all, just because something can be Googled it doesn't mean that it shouldn't be asked on SO. Many people ask questions they know the answer to, just because having an answer to that question might be useful to other people. I had a few candidates for a queue implementation, but googling only yields implementations and no canonical answer. SO is for searching for a canonical and correct answer, not for searching for a random answer. — Jakub Arnold, Nov 25 '14 at 23:33
http://themonadreader.files.wordpress.com/2010/05/issue16.pdf contains an article I wrote on a wide variety of efficient priority queue implementations in Haskell. — Louis Wasserman, Nov 26 '14 at 00:33

score 8 · Accepted Answer · edited Jun 20 '20 at 09:12

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.

score 3 · Answer 2 · answered Nov 14 '16 at 03:20

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

I believe those amortized bounds only hold when the heap is used in a single-threaded fashion. — dfeuer, Nov 14 '16 at 07:17

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

2 Answers2