Binomial Heap Union and Insertion Operations
#techlearners
The procedure of uniting two binomial heaps into one binomial heap
Algorithm: given binomial heaps H1 and H2
Step 1. Merge H1 and H2, i.e. link the roots of H1 and H2 in non-decreasing order.
Step 2. Restoring binomial heap by linking binomial trees of the same degree together: traverse the linked list, keep track of three pointers, Previous, current and next.
Case 1: degrees of current and next are not same, move ahead.
Case 2: If degree of next of next is also same, move ahead.
Case 3: If key of current is smaller than or equal to key of next, make next as a child of current by linking it with current.
Case 4: If key of current is greater than next, then make current as child of next.
Time Complexity of Union Operation O(logn)
The procedure to insert a key in binomial heap
Step 1. create a new binomial heap H1 of one node of value x
Step 2. Unite H1 and H.
Insert Binomial Heap()
1: SET H’ = Create Binomial-Heap()
2: SET Parent[x] = NULL,
Child[x] = NULL and
Sibling[x] = NULL,
Degree[x] = NULL
3: SET Head[H’] = x
4: SET Head[H] = Union Binomial Heap(H, H’)
5: END
Time Complexity of insert operation– O(logn)
TECHLEARNERS BY NEERAJ SAXENA
http://www.techlearners.co.in
On this page of the site you can watch the video online Binomial Heap Union and Insertion Operations with a duration of hours minute second in good quality, which was uploaded by the user Techlearners By Neeraj Saxena 27 November 2020, share the link with friends and acquaintances, this video has already been watched 31,635 times on youtube and it was liked by 367 viewers. Enjoy your viewing!
