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.

Note

The leftist property says that the rank of a left child is greater than or equal to the rank of a right child. The rank of a node is the length of the rightmost path from the node to an empty node. This path is called the right spine of the node. As a result of the leftist property, we get a...