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

Start Free Trial

No credit card required