Algorithm for Binomial Heap Operations
(from CLR text)

Make-Binomial-Heap()
head[H] = NIL
return H



Binomial-Heap-Minimum(H)
y := NIL
x := head[H]
min := infinity
while x <> NIL
      do if key[x] < min
            then min := key[x]
                 y := x
         x := sibling[x]
return y



Binomial-Link(y,z)
p[y] := z
sibling[y] := child[z]
child[z] := y
degree[z] := degree[z] + 1



Binomial-HeapMerge(H1,H2)
a = head[H1]
b = head[H2]
head[H1] = Min-Degree(a, b)
if head[H1] = NIL
    return
if head[H1] = b
   then b = a
a = head[H1]
while b <> NIL
    do if sibling[a] = NIL
          then sibling[a] = b
               return
          else if degree[sibling[a]] < degree[b]
                  then a = sibling[a]
                  else c = sibling[b]
                       sibling[b] = sibling[a]
                       sibling[a] = b
                       a = sibling[a]
                       b = c



Binomial-Heap-Union(H1,H2)
H := Make-Binomial-Heap()
head[H] := Binomial-Heap-Merge(H1,H2)
free the objects H1 and H2 but not the lists they point to
if head[H] = NIL
   then return H
prev-x := NIL
x := head[H]
next-x := sibling[x]
while next-x <> NIL
      do if (degree[x] <> degree[next-x]) or
                (sibling[next-x] <> NIL
                and degree[sibling[next-x]] = degree[x])
            then prev-x := x
                 x := next-x
            else if key[x] <= key[next-x]
                 then sibling[x] := sibling[next-x]
                      Binomial-Link(next-x,x)
                 else if prev-x = NIL
                         then head[H] = next-x
                         else sibling[prev-x] := next-x
                      Binomial-Link(x,next-x)
                      x := next-x
         next-x := sibling[x]
return H



Binomial-Heap-Insert(H,x)
H' := Make-Binomial-Heap()
p[x] := NIL
child[x] := NIL
sibling[x] := NIL
degree[x] := 0
head[H'] := x
H := Binomial-Heap-Union(H,H')



Binomial-Heap-Extract-Min(H)
find the root x with the minimum key in the root list of H,
         and remove x from the root list of H
H' := Make-Binomial-Heap()
reverse the order of the linked list of x's children
        and set head[H'] to point to the head of the resulting list
H := Binomial-Heap-Union(H,H')
return x



Binomial-Heap-Decrease-Key(H,x,k)
if k > key[x]
   then error "hew key is greater than current key"
key[x] := k
y := x
z := p[y]
while z <> NIL and key[y] < key[z]
    do exchange key[y] and key[z]
       if y and z have satellite fields, exchange them, too.
       y := z
       z := p[y]



Binomial-Heap-Delete(H,x)
Binomial-Heap-Decrease-Key(H,x,-infinity)
Binomial-Heap-Extract-Min(H)