The four cases that occur in BINOMIAL-HEAP-UNION. Labels a, b, c, and d serve only to identify the roots involved; they do not indicate the degrees or keys of these roots. In each case, x is the root of a Bk-tree and l > k. (a) Case 1: degree[x] ≠ degree[next-x]. The pointers move one position farther down the root list.
(b) Case 2: degree[x] = degree[next-degree[sibling[next-x]]. Again, the pointers move one position farther down the list, and the next iteration executes either case 3 or case 4.
(c) Case 3: degree[x] = degree[next-x] ≠ degree[sibling[next-x]] and key[x] ≤ key[next-x]. We remove next-x from the root list and link it to x, creating a Bk+1-tree.
(d) Case 4: degree[x] = degree[next-x] ≠ degree[sibling[next-x]] and key[next-x] ≤ key[x]. We remove x from the root list and link it to next-x, again creating a Bk+1-tree.
continue:-uniting3.php
