O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

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

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

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