Haskell Cookbook

Creating and testing a priority queue

In this recipe, we will create and test our own collection priority queue based on a binary tree, and at the same time, we will test it based on its invariant. Many collections and data structures require binary tree as a basic ingredient. 

A priority queue that we will consider is a leftist heap. A leftist heap is implemented as a heap-ordered binary tree. In a heap-ordered binary tree, the value at the node is less than or equal to the values of children. A priority queue is used where we are always interested in the minimum element in the collection and would like to extract or remove it from the collection. The leftist priority queue obeys leftist property.

The leftist property says that the rank ...