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

Functional heaps

Note that if we observe the heap invariant--that is, root elements are never greater than child values--on a leftist tree, we will get a leftist heap.

The preceding tree, for example, is a leftist heap. A notable property of a leftist heap is any path is a sorted list. This helps us efficiently merge the tree after a pop operation.

Where does merge come from? We know the minimum element is at the root. So, when we pop or remove the root element, we will get two leftist trees. If we merge these two, we get back to a sane state (invariants restored) and get the next version of the persistent heap.

The case for inserting a new node could be expressed as a merge again. The new node can be looked at as a singleton tree (a tree with just ...

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