Data Structure Questions and Answers-Binomial and Fibonacci Heap
The main distinguishable characterstic of a binomial heap from a binary heap is that
it allows union operations very efficiently
it does not allow union operations that could easily be implemented in binary heap
the heap structure is not similar to complete binary tree
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
Question 1 Explanation:
The main use of binomial heap is to unify two different heap efficiently.
The number of trees in a binomial heap with n nodes is
Question 2 Explanation:
At each depth there is a binomial tree in a binomial heap.
In a binomial heap the root value is greater than left child and less than right child.
Question 3 Explanation:
Binomial tree used in making binomial heap follows min heap property.
Given the pseudo code, state whether the function for merging of two heap is correct or not?
mergeTree(p, q) if p.root.value <= q.root.value return p.addTree(q) else return q.addTree(p)
Question 4 Explanation:
Binomial heap has a property that root value is less than both the child node's value. So the given function of merging two different heap is correct.
What is order of resultant heap after merging two tree of order k?
Question 5 Explanation:
This could be easily verified by looking at the structure of a binomial heap.
There are 5 questions to complete.