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 one node). This is merged with the existing tree, which adds the new node as a result of this. Here comes the code:

sealed abstract class TreeNode { 
  def rank: Int 
} 

The sealed keyword makes sure we know all the subclasses, as these...