Now the complete algorithm for union operation.UNION function is used here.
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 and2
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
Analysis:-
The running time of BINOMIAL-HEAP-UNION is O(lg n), where n is the total number of
nodes in binomial heaps H1 and H2. We can see this as follows. Let H1 contain n1 nodes and
H2 contain n2 nodes, so that n = n1 + n2. Then H1 contains at most ⌊lg n1⌋+1 roots and H2
contains at most
⌊lg n2⌋+1 roots, and so H contains at most ⌊lg n1⌋+⌊lg n2⌋+2 ≤ 2⌊lg n⌋+2 =
O(lg n) roots immediately after the call of BINOMIAL-HEAP-MERGE. The time to perform
BINOMIAL-HEAP-MERGE is thus O(lg n). Each iteration of the while loop takes O(1) time,
and there are at most
⌊lg n1⌋ + ⌊lgn2⌋ + 2 iterations because each iteration either advances the
pointers one position down the root list of H or removes a root from the root list. The total
time is thus O(lg n).
continue uniting5.php
