Leftist Heaps

For simplicity, we'll continue to work with heaps of Ints.

type alias Rank = Int
    
type Heap = E | T Rank Int Heap Heap

The rank r of a leftist heap is the length of its rightmost spine (that is, the number of edges on the path to the rightmost Empty node, or the number of non-E nodes along this path).

The node T r i left right stores its rank r so that the rank function below does not need to call computeRank to recompute it.

computeRank : Heap -> Rank
computeRank h =
  case h of
    E -> 0
    T r _ left right ->
      let r' = 1 + computeRank right in
      if r == r'
        then r
        else Debug.crash "incorrect rank"

rank h =
  case h of
    E         -> 0
    T r _ _ _ -> r

A few functions on leftist heaps that we will use to state invariants:

value h =
  case h of
    E         -> maxInt
    T _ i _ _ -> i

left h =
  case h of
    E         -> E
    T _ _ a _ -> a

right h =
  case h of
    E         -> E 
    T _ _ _ b -> b

size h =
   case h of
     E         -> 0
     T _ _ a b -> 1 + size a + size b

Invariants

∀h. (value(h) ≤ value(left(h))) ∧ (value(h) ≤ value(right(h)))
∀h. rank(left(h)) ≥ rank(right(h))

In-Class Exercise

Let log = logBase 2.

Prove: ∀h. rank(h) = r ⇒ size(h) ≥ 2^r - 1
Prove: ∀h. size(h) = n ⇒ rank(h) ≤ floor(log(n+1))

Thus, the right spine of a leftist heap h of size n has O(log n) elements.

Merging

Unlike for regular min-heaps, merging leftist heaps runs quickly (faster than O(n)) by taking advantage of the fact that right spines are short (O(log n)).

The helper function makeT creates a T node that stores x and positions h1 and h2 as its children depending on their rank.

makeT : Int -> Heap -> Heap -> Heap
makeT x h1 h2 =
  let (r1,r2) = (rank h1, rank h2) in
  if r1 >= r2
    then T (1+r2) x h1 h2
    else T (1+r1) x h2 h1

The following is an equivalent definition of makeT.

makeT x h1 h2 =
  let (left,right) =
    if rank h1 >= rank h2
      then (h1, h2)
      else (h2, h1)
  in
  T (1 + rank right) x left right

The merge function combines two non-empty heaps by choosing the smaller of their two minimum values and recursively merging, using makeT to place "heavier" subtrees to the left.

merge : Heap -> Heap -> Heap
merge h1 h2 = case (h1, h2) of
  (_, E) -> h1
  (E, _) -> h2 
  (T _ x1 left1 right1, T _ x2 left2 right2) ->
    if x1 <= x2
      then makeT x1 left1 (merge right1 h2)
      else makeT x2 left2 (merge h1 right2)

The makeT function runs in O(1) time. The running time of merge is dominated by its recursive calls. Let n be the size of the larger of the two heaps. The leftist property ensures that the right spine of each heap has O(log n) elements. Because the recursive calls traverse the right spine of one of the input heaps, there are at most O(log n) recursive calls, each of which performs O(1) work. Therefore, merge runs in O(log n) time.

Rest of Interface

empty       = E
singleton x = T 1 x E E

Insertion and deletion can be defined in terms of merge, so each runs in O(log n) time.

insert : Int -> Heap -> Heap
insert x h = merge (singleton x) h

deleteMin : Heap -> Maybe Heap
deleteMin h = case h of
  E         -> Nothing
  T r _ a b -> Just (merge a b)

Implementing the rest of the heap abstraction is straightforward.

findMin : Heap -> Maybe Int
findMin h = case h of
  E         -> Nothing
  T _ i _ _ -> Just i

isEmpty : Heap -> Bool
isEmpty h = h == empty

Our implementation (LeftistHeaps.elm) exports the same type signatures as the vanilla implementation of min-heaps from before.

module LeftistHeaps
  (Heap, empty, isEmpty, findMin, insert, deleteMin, merge) where
  ...

Notice how sequences of inserts pile up elements heavily to the left.

> import LeftistHeaps (..)
> insert 1 <| insert 2 <| insert 3 <| empty
T 1 1 (T 1 2 (T 1 3 E E) E) E : LeftistHeaps.Heap

Reading

Required