Menu
I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children.
I am actually just wondering that what so special in organizing the binomial tree structure in such a way that the first child have on one node second have two third have four and so on?
What if, if we use some normal tree for heaps without restriction of two child and then apply the union procedure and just make one heap the left child of the other heaps?
392
A Fibonacci heap is thus better than a binary or binomial heap when b is smaller than a by a non-constant factor. It is also possible to merge two Fibonacci heaps in constant amortized time, improving on the logarithmic merge time of a binomial heap, and improving on binary heaps which cannot handle merges efficiently.
The fundamental distinction is that whereas the Binary Search Tree does not allow duplicates, the Heap allows. The BST is ordered, while Heap is not. So, if order is important, BST is the way to go.
The main application of Binary Heap is as implement a priority queue. Binomial Heap is an extension of Binary Heap that provides faster union or merge operation with other operations provided by Binary Heap.
the location of child node is not fixed i.e child nodes could be at level (h-2) or (h-3), where h is height of heap and h>4.
The key difference between a binary heap and a binomial heap is how the heaps are structured. In a binary heap, the heap is a single tree, which is a complete binary tree. In a binomial heap, the heap is a collection of smaller trees (that is, a forest of trees), each of which is a binomial tree. A complete binary tree can be built to hold any number of elements, but the number of elements in a binomial tree of some order n is always 2n. Consequently, we only need one complete binary tree to back a binary heap, but we may need multiple binomial trees to back a binomial heap. Interestingly, the orders of the binomial trees used in a binomial heap correspond to the 1 bits set in the binary representation of the number of elements in the forest.
The reason for organizing binomial heaps as they are is that a binomial tree of order n always has exactly 2n nodes in it. This allows us to make assumptions about the number of elements in the binomial tree without actually having to inspect the structure of that tree. On the other hand, a complete binary tree of some height h may have a variable number of nodes in it depending on how the last row is filled out. The fact that each of the children must have a very precisely-defined structure can also be used to prove that the number of children is at most O(log n), where n is the total number of nodes in the heap, which means that the cost of a delete-min is not too large.
An important detail behind this is that a binomial heap is not any tree that happens to have k children. It's a tree that's rigorously defined as
(Technically, the order 0 special case isn't necessary here). You can see this here:
Note that there is exactly one tree of each order, with no flexibility at all in the number or position of the nodes.
However, an important alternative definition is the following:
(Take a minute to see why these are equivalent). Using this second definition, it's a quick induction proof to show that the number of nodes in the tree is 2n. As a base case, a tree of order 0 has 20 = 1 nodes as required. For the inductive step, if we have two trees of order n - 1, they collectively have 2n-1 + 2n-1 = 2n nodes as required. Thus the total number of nodes in a binomial tree of order n is exactly 2n.
The idea for a heap that you're describing in your final paragraph does not always lead to an efficient runtime. In particular, if you have trees with a huge branching factor and no other structural constraints, then you could in theory build a heap of n nodes consisting of a single node with (n - 1) children. In that case, after deleting the minimum element from the heap, you'd have to look at all n - 1 children to determine which was the new minimum, giving a runtime of O(n). The other structural constraints on trees like complete binary trees, binomial trees, etc. guarantee that this worst-case doesn't happen.
Hope this helps!
138
add on to great answer above provided by templatetypedef. Here is a visual table to show different time complexity on different operations
╔══════════════╦═══════════════════════╦════════════════════════╗ ║ Operation ║ Binary ║ Binomial ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ ║ ║ ║ ║ insert ║ O(logN) ║ O(logN) ║ ║ ║ ║ ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ find Min ║ O(1) ║ O(logN) ║ ║ ║ ║ ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ ║ ║ ║ ║ Revmove ║ O(logN) ║ O(logN) ║ ║ ║ ║ ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ ║ ║ ║ ║ Decrease Key ║ O(logN) ║ O(logN) ║ ║ ║ ║ ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ ║ ║ ║ ║ Union ║ O(N) ║ O(logN) ║ ║ ║ ║ ║ ╠══════════════╬═══════════════════════╬════════════════════════╣ ║ ║ ■ Min element is root ║order k binomial tree Bk║ ║ ║ ■ Heap height = logN ║ ■ Number of nodes = 2k.║ ║ ║ ║ ■ Height = k. ║ ║ ║ ║ ■ Degree of root = k. ║ ║ Useful ║ ║ ■ Deleting root yields ║ ║ Properties ║ ║ binomial trees ║ ║ ║ ║ Bk-1, … , B0. ║ ║ ║ ║ (see graph below) ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ╚══════════════╩═══════════════════════╩════════════════════════╝ I got this image from the Princeton lecture slides
Binary Heap: (almost complete binary tree) 
Binomial Heap:
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
