Binomial Heap Operations

BINOMIAL-HEAP-MERGE merges the root lists of H1 and H2 into a single linked list
that is sorted by degree into monotonically increasing order. Similar to MERGE of MERGESORT.

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 //Cases 1 and 2
12              x ← next-x // Cases 1 and 2
13   else if key[x] ≤ key[next-x]
14              then sibling[x] ← sibling[next-x] // Case 3
15                   BINOMIAL-LINK(next-x, x) // Case 3
16   else if prev-x = NIL // Case 4
17              then head[H] ← next-x ▹ Case 4
18   else sibling[prev-x] ← next-x ▹ Case 4
19        BINOMIAL-LINK(x, next-x) ▹ Case 4
20        x ← next-x ▹ Case 4
21   next-x ← sibling[x]
22 return H

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')