Operations on binomial heaps

Algorithm to find minimum
Input	Binomial heap .
Output	pointer of minimum key
Complexity	O(lgn).

BINOMIAL-HEAP-MINIMUM(H)
1      y= NIL
2      x = head[H]
3     min = ∞
4     while x ≠ NIL
5        do  if key[x] < min
6                  then min = key[x]
7                          y =x
8               x = sibling[x]
9 return y

Algorithm for union operation
Input	Two Binomial heap H1 and H2  .
Output	Head pointer of final Binomial heap
Complexity	O(lgN).

BINOMIAL-LINK(y, z)
    1 p[y] =z
    2 sibling[y] = child[z]
    3 child[z] =y
    4 degree[z] = degree[z] + 1


BINOMIAL-HEAP-UNION (H1, H2)
1 H = MAKE-BINOMIAL-HEAP ( )
2 head [H] = BINOMIAL-HEAP-MERGE(H1, H2)
3 free the objects H1 and H2 but not the lists they point to
4 if head[H] = NIL
5 then return H
6 prev-x =NIL
7 x =head[H]
8 next-x = sibling[x]
9 while next-x ≠ NIL
10 do if (degree[x] ≠ degree[next-x]) or
     (sibling[next-x] ≠ NIL and degree[sibling[next-x]] =degree[x])
11 then prev-x = x 
12 x = next-x 
13 else if key[x] ≤ key[next-x]
14 then sibling[x] = sibling[next-x] 
15 BINOMIAL-LINK(next-x, x) 
16 else if prev-x = NIL 
17 then head[H] = next-x 
18 else sibling[prev-x] =next-x 
19 BINOMIAL-LINK(x, next-x) 
20 x =next-x 
21 next-x = sibling[x]
22 return H

Binomial heap insertion
Input	Binomial heap .
Output	pointer of minimum key
Complexity	O(logn).

BINOMIAL-HEAP-INSERT(H, x)
1 H′ = MAKE-BINOMIAL-HEAP()
2 p[x] = NIL
3 child[x] = NIL
4 sibling[x] =NIL
5 degree[x] = 0
6 head[H′] = x
7 H = BINOMIAL-HEAP-UNION(H, H′)

Binomial heap extract min.
Input	Binomial heap .
Output	pointer of the extracted node
Complexity	O(logn).

BINOMIAL-HEAP-EXTRACT-MIN(H)
1 find the root x with the minimum key in the root list of H,
and remove x from the root list of H
2 H′ = MAKE-BINOMIAL-HEAP()
3 reverse the order of the linked list of x's children,
and set head[H′] to point to the head of the resulting list
4 H = BINOMIAL-HEAP-UNION(H, H′)
5 return x;

Binomial heap decrease key.
Input	Binomial heap .
Output	Binomial heap after decrease key
Complexity	O(logn).

BINOMIAL-HEAP-DECREASE-KEY(H, x, k)
1 if k > key[x]
2 then error "new key is greater than current key"
3 key[x] =k
4 y = x
5 z = p[y]
6 while z ≠ NIL and key[y] < key[z]
7 do exchange key[y] = key[z]
8  If y and z have satellite fields, exchange them, too.
9 y =z
10 z = p[y]

Binomial heap delete key.
Input	Binomial heap .
Complexity	O(logn).

BINOMIAL-HEAP-DELETE(H, x)
        1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)
         2 BINOMIAL-HEAP-EXTRACT-MIN(H)