Learning Functional Data Structures and Algorithms

Leftist trees

Think about the problem we'd face if we try to adapt this array-based algorithm to a persistent version. The swap will result in expensive copying, so an insert/pop would have complexity amounting to O(n).

A leftist tree is a data structure that we can use to implement the priority queue ADT. Before you look at the core data structure, look at the rank of the tree.

We first make the tree a full binary tree. If we put explicit leaves in such a tree, every node (other than the leaves) will have two children.

For more information, visit:

http://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre

Let's have a look at the figure now:

We define the rank of a binary tree as per ...