4. Consider the following two methods for implementing the buildHeap function fo
ID: 643286 • Letter: 4
Question
4. Consider the following two methods for implementing the buildHeap function for a binomial heap. (a) The first method is to represent all the input values as Bo trees and to merge them one at a time into an initially empty heap. We can estimate the run time of this approach by considering the number of bits that change when repeatedly adding one to binary to a number that is initially zero. Develop an expression for the run time of this version of buildHeap in terms of N, where N = 2^P (b) The second method is to represent all the input values as B0 trees, place them on a queue, then repeatedly take two trees from the head of the queue, merge them, and put the resulting tree on the back of the queue. This process is repeated until the queue contains only one tree. Develop an expression for the run time of this version of buildHeap in terms of N, where N = 2^p. (c) Considering all factors, which method is best? Explain.Explanation / Answer
(a).
Binomial heap is a set of binomial tree that satisfies the following binomial properties.
Each binomial tree in N follows the min-heap property: the key of a node is greater than or equal to the key of its parent. We say that each such tree is min-heap-ordered.
For any nonnegative integer k, there is at most one binomial tree in N whose root has degree k.
Consider the following steps which will analyses the whole algorithm which has been given in the problem.
Insert: Sequence of insertion
If N= …….0, then only 1 steps.
If N = …….01, then only 2 steps.
If N = …….011, then only 3 steps.
If N = …….0111, then only 4 steps.
Inserting one element in the binomial heap will take O (log N) time.
If N = 1111…………1111, then log N steps.
Starting from an empty binomial heap, a sequence of n consecutive operation takes O(n)
time. This is same as the binary heap. The prove of this algorithm is as follows:
(n/2) (1) + (n/4) (2) + (n/4) (2) + (n/4) (2) + (n/4) (2) + (n/4) (2) + …………. <= 2n.
The insert operation of binomial algorithm is as follows:
Binomial-Heap-Insert (Heap, Element)
New Make-Binomial-Heap ()
head[New] Element
parent[New] Element
sibling[New] NIL
child[New] NIL
degree[New] 1
Binomial-Heap-Unify (Heap, New)
Merging: Merging of the two-binomial tree in a single tree will take the log N time. The algorithm to merge the two-binomial tree is as follow:
BINOMIAL-HEAP-MERGE (H1, H2) {
H MAKE-BINOMIAL-HEAP ()
if key[head[H2]] < key[head[H1]] then
head[H] head[H2]
current2 sibling[head[H2]]
current1 head[H1]
else
head[H] head[H1]
current1 sibling[head[H1]]
current2 head[H2]
current head[H]
while current1 NIL and current2 NIL
do
if key[current1] > key[current2] then
sibling[current] current2
current sibling[current]
current2 sibling[current2]
else
sibling[current] current1
current sibling[current]
current1 sibling[current1]
if current1 = NIL
tail current2
else
tail current1
while tail NIL
do
sibling[current] tail
current sibling[current]
tail sibling[tail]
return head[H]
}
(b).
Step1: In the second approach the binomial heap is being implemented using the queue. In which we are first extracting the two-binomial tree from the queue and merging them using the following algorithms.
BINOMIAL-HEAP-MERGE (H1, H2) {
H MAKE-BINOMIAL-HEAP ()
if key[head[H2]] < key[head[H1]] then
head[H] head[H2]
current2 sibling[head[H2]]
current1 head[H1]
else
head[H] head[H1]
current1 sibling[head[H1]]
current2 head[H2]
current head[H]
while current1 NIL and current2 NIL
do
if key[current1] > key[current2] then
sibling[current] current2
current sibling[current]
current2 sibling[current2]
else
sibling[current] current1
current sibling[current]
current1 sibling[current1]
if current1 = NIL
tail current2
else
tail current1
while tail NIL
do
sibling[current] tail
current sibling[current]
tail sibling[tail]
return head[H]
}
Step 2: After merging both the binomial tree. It is needed to insert the binomial tree in the queue for that must use the following algorithm.
Binomial-Heap-Insert (Heap, Element)
{
New Make-Binomial-Heap ()
head[New] Element
parent[New] Element
sibling[New] NIL
child[New] NIL
degree[New] 1
Binomial-Heap-Unify (Heap, New)
}
Step 3: repeat both the steps until there is only one binomial tree left in the queue.
If the root lists of H1 and H2 have m roots altogether, BINOMIAL-HEAP-MERGE runs in O(m) time by repeatedly examining the roots at the heads of the two root lists and appending the root with the lower degree to the output root list, removing it from its input root list in the process.
(c).
Take the first algorithm.
The first algorithm is to constructing the binomial heap using insertion algorithm and merging the binomial tree to make the final the binomial tree. The total time complexity is to complete this task would be N log N. As merging operation, itself takes the 2log N time.
Whereas, the second approach is taking log N time to extract the tree from the queue for the first time and again merge the both the tree in a single tree and insert that in the queue again. By doing this it takes the time as below:
= 2*extraction + merging the both the tree + inserting the tree.
= 2* log N + log N + log N
= 4 log N time
Therefore, the time complexity is = O (4log N)
By comparing first and second approach, we can say that the first approach is better than the second one.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.