Binomial Heaps

Our implementation (BinomialHeap.elm) exports the same type signatures as the previous implementations of min-heaps.

Binomial Trees: Representation and Invariants

type alias Rank =
  Int

type Tree a =
  Node Rank a (List (Tree a))

rank (Node r _ _) = r
root (Node _ x _) = x

Binomial trees of rank r are defined inductively as follows.

  • Node 0 n [] is a binomial tree of rank 0.
  • Node r n ts is a binomial tree of rank r > 0 if ts is a list of r binomial trees with rank r-1 through 0, respectively.

A binomial tree of rank r has 2r nodes.

Linking

A binomial tree of rank r + 1 is formed by linking together two trees of rank r, making one the leftmost child of the other.

The link function below links two binomial trees, choosing to keep the smaller of the two elements at the root. Therefore, if t1 and t2 are both heap-ordered, then so is the result.

link : Tree comparable -> Tree comparable -> Tree comparable
link t1 t2 =
  let
    (Node r x1 ts1) = t1
    (Node _ x2 ts2) = t2
  in
  if x1 <= x2 then
    Node (r+1) x1 (t2::ts1)
  else
    Node (r+1) x2 (t1::ts2)

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

Binomial Heaps: Representation and Invariants

type Heap a =
  Heap (List (Tree a))

A binomial heap is list of heap-ordered binomial trees, kept in strictly-increasing order of rank. A binomial heap containing n elements is represented using O(log n) binomial trees, analogous to how the binary representation of n requires O(log n) bits.

Heap Interface

empty : Heap comparable
empty =
  Heap []

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

The findMin function searches for the smallest root among all of the binomial trees, taking O(log n) time.

findMin : Heap comparable -> Maybe comparable
findMin (Heap ts) =
  case List.map root ts of
    [] ->
      Nothing
    n::ns ->
      Just (List.foldl min n ns)

See Homework 4 for a way to implement findMin so that it runs in O(1) time, as for other heap implementations.

Insertion

Inserting into a binomial heap requires pairwise linking of Trees with equal rank. Think of how to "sum" two bits for binary arithmetic.

insert : comparable -> Heap comparable -> Heap comparable
insert x (Heap ts) =
  Heap (insertTree (Node 0 x []) ts)

insertTree : Tree comparable -> List (Tree comparable) -> List (Tree comparable)
insertTree t ts =
  case ts of
    [] ->
      [t]
    t1::ts1 ->
      if rank t == rank t1 then
        insertTree (link t t1) ts1
      else {- if rank t < rank t1 then -}
        t :: ts

There are O(m) recursive calls to insertTree (where m is the length of ts), each of which performs O(1) work (to link two trees). Thus, insert runs in O(m) = O(log n) time.

Merging

merge : Heap comparable -> Heap comparable -> Heap comparable
merge (Heap ts1) (Heap ts2) =
  Heap (merge_one_pass ts1 ts2)

Merging in One Pass

Compared to the "two-pass" solution from the textbook (described below), we will consider an alternative, one-pass definition (drawn from this post) that is slightly easier to analyze.

merge_one_pass
    : List (Tree comparable) -> List (Tree comparable)
   -> List (Tree comparable)
merge_one_pass ts1 ts2 =
  case (ts1, ts2) of
    ([], _) ->
      ts2
    (_, []) ->
      ts1
    (t1::ts1_rest, t2::ts2_rest) ->
      if rank t1 < rank t2 then
        t1 :: merge_one_pass ts1_rest ts2
      else if rank t2 < rank t1 then
        t2 :: merge_one_pass ts1 ts2_rest
      else
        merge_wc (link t1 t2) ts1_rest ts2_rest

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



Think of how to "sum" two bits with a third "carry" bit for binary arithmetic.

merge_wc
    : Tree comparable -> List (Tree comparable) -> List (Tree comparable)
   -> List (Tree comparable)
merge_wc t ts1 ts2 =
  case (ts1, ts2) of
    ([], _) ->
      insertTree t ts2
    (_, []) ->
      insertTree t ts1
    (t1::ts1_rest, t2::ts2_rest) ->
      let
        (r,r1,r2) = (rank t, rank t1, rank t2)
      in
      if r < r1 && r < r2 then
        t :: merge_one_pass ts1 ts2
      else if r < r1 && r == r2 then
        merge_wc (link t t2) ts1 ts2_rest
      else if r == r1 && r < r2 then
        merge_wc (link t t1) ts1_rest ts2
      else {- if r == r1 && r == r2 then -}
        t :: merge_wc (link t1 t2) ts1_rest ts2_rest

Let T(m) and S(m) be the running times of the mutually recursive merge_one_pass and merge_wc functions, respectively, where m is an upper bound on the number of trees in both input lists combined.

  • merge_one_pass has two base cases...

    • Cases 1 and 2: T(m) = O(1)

    ... and three recursive cases:

    • Cases 3 and 4: T(m) = O(1) + T(m-1)
    • Case 5: T(m) = O(1) + S(m-2)

  • merge_wc has two base cases...

    • Cases 1 and 2: S(m) = O(m)

    ... and four recursive cases:

    • Case 3: S(m) = O(1) + T(m)
    • Cases 4 and 5: S(m) = O(1) + S(m-1)
    • Case 6: S(m) = O(1) + S(m-2)

How many times do these functions recurse? merge_one_pass recursively calls either itself or merge_wc, but always with smaller inputs (T(m-1) and S(m-2), respectively). Thus, it makes O(m) recursive calls. merge_with_wc calls either merge_one_pass with input of the same size (T(m)) or itself with smaller inputs (S(m-1) or S(m-2)). Even when hitting only the former case, the recursion terminates with O(m) calls because merge_one_pass does. Thus, overall, we have O(m) recursive calls, each of which performs O(1) work.

To complete the analysis, consider the base cases. The base cases for merge_wc perform O(m) work, so the running time for merge_wc is O(m)+O(m) = O(m) time. The base cases for merge_one_pass perform O(1) work, so the running time for merge_one_pass is O(m). That is, O(log n) time.

Merging in Two Passes (Optional)

The following (singly-recursive) version is shorter:

merge_two_pass
    : List (Tree comparable) -> List (Tree comparable)
   -> List (Tree comparable)
merge_two_pass ts1 ts2 =
  case (ts1, ts2) of
    ([], _) ->
      ts2
    (_, []) ->
      ts1
    (t1::ts1_rest, t2::ts2_rest) ->
      if rank t1 < rank t2 then
        t1 :: merge_two_pass ts1_rest ts2
      else if rank t2 < rank t1 then
        t2 :: merge_two_pass ts2_rest ts1
      else
        insertTree (link t1 t2) (merge_two_pass ts1_rest ts2_rest)

To analyze the running time of merge_two_pass, let m be the total number of trees in both ts1 and ts2. The first two cases run in O(1) time. Each recursive call to merge_two_pass decreases m by one (in the third and fourth cases) or two (in the fifth case). The cons operations in the third and fourth cases require O(1) work. In the fifth case, link requires O(1) time, insertTree requires O(m) time, and the recursive call to merge_two_pass requires T(m-2) time. There are O(m) recursive calls, each of which requires at most O(m) time. The result is a O(m2) running time, which is O(log2(n)) where n is the total number of elements described in the two heaps being merged.

A more subtle analysis, however, can be used to argue that the implementation of merge_two_pass runs in O(log n) time. The argument requires a more careful accounting of how many times link is called (which is the crux of both insertTree and merge_two_pass) based on the analogy between merging lists and adding two numbers in binary representation.

Deletion

removeMinTree
    : List (Tree comparable)
   -> (Tree comparable, List (Tree comparable))
removeMinTree ts =
  case ts of
    []  ->
      Debug.todo "removeMinTree: impossible"
    [t] ->
      (t, [])
    t::ts_rest ->
      let
        (minTree, restTrees) = removeMinTree ts_rest
      in
      if root t < root minTree then
        (t, ts_rest)
      else
        (minTree, t::restTrees)

deleteMin : Heap comparable -> Maybe (comparable, Heap comparable)
deleteMin (Heap ts) =
  case ts of
    [] ->
      Nothing
    _  ->
      let (Node _ x ts1, ts2) = removeMinTree ts in
      Just (x, Heap (merge (List.reverse ts1) ts2))

deleteMin runs in O(log n) + O(log n) = O(log n) time.

Finding (Revisited)

We can reuse the removeMinTree helper function to reimplement findMin.

findMin (Heap ts) =
  case ts of
    [] ->
      Nothing
    _  ->
      Just (root (Tuple.first (removeMinTree ts)))

Exercise: Non-Empty Lists

The Debug.todo in removeMinTree is a bummer: the arguments to all calls of removeMinTree are very clearly non-empty lists. Redefine removeMinTree to encode this invariant into its type:

type alias NonEmptyList =
  (a, List a)

removeMinTree
    : NonEmptyList (Tree comparable)
   -> (Tree comparable, List (Tree comparable))


Reading

Required

  • Okasaki, Chapter 3.2