O'Reilly logo

Haskell Cookbook by Yogesh Sajanikar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required