Lecture Notes for CS 512, Algorithm Design

Binomial Heaps - 21 February 2000

1. how do you merge two binary heaps

   1. copy one into the other and heapify

   2. can heap merging be cheaper than O(n)?

2. how many ways can k items be picked from a set of n items?

   1. pick one of n, then pick one of n - 1, ..., then pick one of n - (k - 1)

   2. there are n(n - 1)...(n - (k - 1)) = n!/(n - k)! ways to do that

   3. but, any set of k items can be picked k(k - 1)...(1) = k! ways, all of which are the same

   4. n choose k = choose(n, k) = n!/(k!(n - k)!)

3. binomial trees

   1. B_k, the ordered binomial tree of degree k

      1. B₀ is a single node

      2. B_k is two B_{k - 1} trees, the left-most child of one being the other

   2. properties of B_k

      1. it has 2_k nodes

      2. it has height k

      3. it has choose(k, i) nodes at level i

      4. left-to-right children of the root are B_{k - 1}, B_{k - 2}, ..., B₀

   3. arbitrary numbers of ordered children - implemented with child-sibling pointers in each node

      1. struct bmt_node { int key, degree; bmt_node * child, * sibling, * parent}

      2. link two B_k trees to form a B_{k + 1} tree

4. binomial heaps

   1. a set of binomial trees

      1. each tree obeys the heap property

      2. there is at most one tree of degree k in the heap

         1. the binary representation of the number of nodes in the heap

   2. use the unused sibling pointer in each tree root to make the heap.

5. operations

   1. make a new heap - constant time

   2. find the minimum in the heap - log n time

   3. join two heaps - merge the two tree sets, merge the trees, log n

   4. add a new node - merge with a one-node heap - log n

   5. find and delete the minimum - form a new heap and merge with the old - log n time

   6. use a new, lower key value - heapify, log n time

   7. delete a key - reset to min and delete, log n time

This page last modified on 28 February 2000.