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 ...
Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
