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