The simplest Haskell Priority Queue implementation I know of

Posted in: haskell, data-structures.

Nothing about what I’m going to say is novel or particularly mind-blowing, but yet useful, especially on programming competitions websites like HackerRank. This implementation is shamelessly stolen from Okasaki’s book.

A Priority Queue can be easily implemented in an imperative setting but is not totally obvious how that could efficiently translate into a functional language, especially in a pure language like Haskell.

See this blog post for another excellent implementation, but in OCaml (always based on Okasaki).

This is a Literate Haskell post. Let’s begin with the usual importing fandango:

“Leftist heaps always keeps the left branches of all roots being the longer and in worst case, they are as long as the right branches. In other word, all right branches of all roots are shortest. In order to maintain this property, each node has a rank, which indidates the length of the path between the node and the right most leaf.” – 1

makeHeap is straightforward: we compare the two ranks, and we preserve the leftist property by setting as the rank the min of the two, and storing as the right child the smallest (aka with smallest rank) child.


Loved this post? Stay update!