Leftist Heaps

Watch the video first, and try to work through and code up the various pieces that come up during the pauses. If you get stuck somewhere, you can peek at the reading and solutions below (scroll slowly!). But then get back to working through the tasks before reading everything below in full.

Regularly scheduled programming below...

type alias Rank = Int
    
type Heap a
  = E
  | T Rank a (Heap a) (Heap a)

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 ->
      if r == (1 + computeRank right)
        then r
        else Debug.todo "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         -> Nothing
    T _ x _ _ -> Just x

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

Min-Heap Property: ∀h. (left(h) ≠ E ⇒ value(h) ≤ value(left(h))) ∧ (right(h) ≠ E ⇒ value(h) ≤ value(right(h)))
Leftist Heap Rank Property: ∀h. rank(left(h)) ≥ rank(right(h))

In-Class Exercise

Prove: ∀h. size(h) ≥ 2^rank(h) - 1
Corollary: ∀h. rank(h) is O(log(size(h))). That is, the right spine of a leftist heap h of size n has O(log n) elements.

Merging

Unlike for array-based 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 : a -> Heap a -> Heap a -> Heap a
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

(Note: The following depicts the definition of makeT and also defines an "infix graphical operator" (the upside-down T) makeT that will be used in subsequent pictures.)

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

To combine two non-empty heaps, the merge function chooses the smaller of their two minimum values and recursively merges, using makeT to place "heavier" subtrees to the left.

merge : Heap comparable -> Heap comparable -> Heap comparable
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)

(Note: The following defines the picture + to refer to merge.)

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 : Heap comparable
empty = E

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

findMin : Heap comparable -> Maybe comparable
findMin h =
  case h of
    E         -> Nothing
    T _ x _ _ -> Just x

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

insert : comparable -> Heap comparable -> Heap comparable
insert x h =
  merge (T 1 x E E) h

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

Our implementation (LeftistHeap.elm) exports the same type signatures as the array-based implementation of min-heaps from before.

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

Take it for a quick spin:

> import LeftistHeap exposing (..)
> makeHeap = List.foldl insert empty
<function> : List comparable -> Heap comparable
> makeHeap (String.toList "abcd")
T 2 'a' (T 1 'b' E E) (T 1 'c' (T 1 'd' E E) E) : Heap Char
> makeHeap (String.toList "dcba")
T 1 'a' (T 1 'b' (T 1 'c' (T 1 'd' E E) E) E) E : Heap Char

cs223

Leftist Heaps

Invariants

Merging

Rest of Interface

Reading

Required

Additional