![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656063235357-Article.jpg\")
<\/p>\n<\/p>\n
The binomial heap in data structure stands as a true marvel, combining the elegance of binary trees with the efficiency of heap-based operations. Born from the ingenuity of computer scientists Peter Bayer and Michael Dietz in 1978, the binomial heap has since become a fundamental building block in various algorithmic applications. Its ability to support rapid insertion, deletion, and merging operations has made it a go-to choice for optimizing complex data manipulation tasks.<\/p>\n
In this article, we embark on a journey into the world of the binomial heap – a versatile, self-balancing data structure. We dive deep into its foundational principles, exploring how the structure leverages the power of binomial trees to perform efficiently even with large datasets. Unraveling its inner workings, we uncover the mechanics of merging and consolidating binomial trees, which form the crux of its efficiency.<\/p>\n
A binomial heap is a specialized tree-based data structure in computer science and a type of heap data structure. The min-heap has a property in that each node in the heap has a value lesser than the value of its child nodes. Binomial heaps are designed to efficiently support various operations, making them a powerful tool in algorithm design and data manipulation tasks. At its core, a binomial heap is a collection of binomial trees, which are defined as a set of binary trees obeying specific rules. A binomial tree of order k is a rooted tree with the following properties:<\/p>\n
Let\u2019s see, binomial heap example:- <\/p>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656063259548-Image-01.png\")
<\/p>\n
A binomial tree of order 0 has a single node. A binomial tree of order k can be made by taking two binomial trees of order k-1 and making one of them as the leftmost child of the other.
\nA Binomial Tree of order k has the properties which are listed below:<\/p>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656063289722-Image-02.png\")
<\/p>\n
A binomial heap that has n nodes consists of the binomial trees equal to the number of 1 bit in the binary representation of n.
\nFor better understanding let’s look into an example, suppose a binomial heap with 9 nodes is to be created. 1001 will be the binary representation of 9. In the binary representation of 9, digit 1 occurs at 0 and 3 positions, so the binomial heap will contain the binomial trees of 0 and 3 degrees.<\/p>\n
The central function in Binomial Heap is the union(), all other functions mainly use this function. The union() operation is used to merge two Binomial Heaps into one. Let us first discuss other functions, we will discuss union later.<\/p>\n
insert(H, k):<\/strong> In this function, a key \u2018k\u2019 is inserted to Binomial Heap \u2018H\u2019. This function firstly creates a Binomial Heap with one key \u2018k\u2019, then calls union on binomial heap \u2018H\u2019 and the new Binomial heap. <\/p>\n getMin(H):<\/strong> This function is used to get the minimum key from the binomial heap. To getMin() is to iterate over the list of roots of Binomial Trees and return the smallest key. O(Logn) will be the time complexity of this function. we can optimize this function to O(1) by maintaining a pointer that will always point to the minimum key root. <\/p>\n extractMin(H):<\/strong> This function uses union() function. Firstly, we call getMin() to find the minimum key of the Binomial Tree, then we will delete that node and create a new Binomial Heap by connecting all subtrees of the removed minimum node. At last, we will call the union() function on the binomial heap \u2018H\u2019 and the newly created Binomial Heap. O(Logn) will be the time complexity. <\/p>\n Two Binomial Heaps H1 and H2 are given, the union(H1, H2) function will create a single Binomial Heap. <\/p>\n Initially merge the two Heaps in non-decreasing order of degrees. In the following diagram, figure(b) shows the result after merging. Case 1:<\/strong> If Orders of x and next-x are not the same, we will move ahead. <\/p>\n<\/li>\n In the next 3 cases, the orders of x and next-x are the same. <\/p>\n<\/li>\n Case 2:<\/strong> If the order of next-next-x is also the same, simply move ahead.<\/p>\n<\/li>\n Case 3:<\/strong> If the key of x is smaller than or equal to the key of next-x, then make next-x as a child of x. <\/p>\n<\/li>\n Case 4:<\/strong> If the key of x is greater than the key of next-x, then make x as the child of next by linking it with next.<\/p>\n<\/li>\n<\/ul>\nUnion function in Binomial Heap:<\/h3>\n
\nAfter the merging, we have to check that there must be at most one Binomial Tree of any order. If there is more than one binomial tree then we need to combine Binomial Trees of the same order. We traverse the list of merged roots, we keep track of three-pointers, prev, x, and next-x. The following 4 cases might arise when we traverse the list of roots. <\/p>\n\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656063313011-Image-03.png\")
<\/p>\nCode Implementation<\/h4>\n\t\t\t\t\t\t