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:
Let's have a look at the figure now:
We define the rank of a binary tree as per the length of its right spine. The rank of the leaf is 0. In the preceding figure, the rank of the tree at root 9 is 2 as we need to cross over the right node with value 27. The right spine for every node is drawn with a dashed line.
A leftist tree is...
