Before knowing about UNION procedure its important to know about different cases which can occur while execution of union of two binomial heaps.There may occur situation when three(3) roots of same degree appear on the root list H at some time.It can happen in the intermediate node while merging.So,there exits some cases based on that we decide whether to link x and next-x based on their degrees and possibly the degree of sibling[next-x].
Throughout the procedure, we maintain three pointers into the root list:
• x points to the root currently being examined,
• prev-x points to the root preceding x on the root list: sibling[prev-x] = x (since initially x has no predecessor, we start with prev-x set to NIL), and
• next-x points to the root following x on the root list: sibling[x] = next-x.
Case 1,occurs when degree[x] ≠ degree[next-x],
that is, when x is the root of a Bk-tree and next-x is the root of a Bl-tree for some l > k. . We don't link x and next-x, so we simply march the pointers one position farther down the list. Updating next-x to point to the node following the new node x .
Case 2, occurs when x is the first of three roots of equal degree, that is, when
degree[x] = degree[next-x] = degree[sibling[next-x]].
We handle this case in the same manner as case 1: we just march the pointers one position farther down the list. The next iteration will execute either case 3 or case 4 to combine the
second and third of the three equal-degree roots.
Cases 3 and 4 occur when x is the first of two roots of equal degree, that is, when
degree[x] = degree[next-x] ≠ degree[sibling[next-x]].
These cases may occur in any iteration, but one of them always occurs immediately following case 2. In cases 3 and 4, we link x and next-x. The two cases are distinguished by whether x or next-x has the smaller key, which determines the node that will be the root after the two are linked.
In case 3, key[x] ≤ key[next-x], so next-x is linked to x.
In case 4, next-x has the smaller key, so x is linked to next-x.
Following either case 3 or case 4, the setup for the next iteration of the while loop is the same. We have just linked two Bk-trees to form a Bk+1-tree, which x now points to. There were
already zero, one, or two other Bk+1-trees on the root list resulting from BINOMIAL-HEAP MERGE, so x is now the first of either one, two, or three Bk+1-trees on the root list. If x is the
only one, then we enter case 1 in the next iteration: degree[x] ≠ degree[next-x]. If x is the first of two, then we enter either case 3 or case 4 in the next iteration. It is when x is the first of
three that we enter case 2 in the next iteration. for further info click:-uniting2.php
