CSCI 570 Episode 2

Binomial heap

• Heap property => each element’s key ≤ keys of it’s children
  popMin() => pop the root element and replace it with the last leaf of the binomial heap
• push() => push the new key to the last leaf then bubble it up to ensure the heap property is satisfied
• decreaseKey() => similar to push, take an arbitrary node, decrease it’s key and then bubble it up to ensure heap property is satisfied

Binomial trees properties => In a binomial tree of degree k

• the root has k children
• the tree has 2^k elements
• the tree has height k
• the children of root are binomial trees of degree k-1, k-2, …,1,0

Defining a binomial heap

• consists of a collection of binomial trees, each one a heap and at most one tree of each degree.
• In a given binomial heap of n items :
  the binary digits of n tell us which degree trees are present
  the longest tree has degree floor( log (n) ) and there are ≤ floor( log (n) ) + 1 trees