A valid binomial min heap A contains n items. A further n items are held in arbi

Question

A valid binomial min heap A contains n items. A further n items are held in arbitrary order in array B[]. They are to be inserted into the binomial heap A. Describe in English a fast algorithm for this operation and state its runtime in 'Big O' notation. A valid binary min heap contains n items and has been built in array A[]. A[] has size greater than 2n. A further n items are held in arbitrary order in array B[]. They are to be inserted into the heap in array A. Describe in English a fast algorithm for this operation and state its runtime in 'Big O' notation.

Explanation / Answer

a) The Binomial heap illustrates the priority queue, which is a collection of binomial trees.

There are many functions available for the binomial heap, but to find the Valid binomial min heap, we can use the following function as follows:-

getMin(H): The best way to find the valid binomial heap is to use the getMin() for traversing the no. of list which is the root of Binomial Trees and at last gives the result by returning the minimum key. This instruction for binomial heap requires O(Logn) time complexity.

Algorithm:-

// Place the algorithm name and pass the parameter as Z
Binomial-Heap-Minimum-Value(Z)
// declare variable as a
a NIL
// declare another variable b
b head[Z]
// state the min value
min
// apply the while loop
while b NIL

      do if key[b] < min
// check the min-value from the list of keys and values pair
           then min key[b]
// view the result of the variable
                y b
// apply the sibling array to find min-value
        b sibling[b]
// returns the result
return a

Finally, The runtime for 'Big 0 notation for binomial heap is "0(log n)"

b) The second equation states to find the valid binary min heap from the set of built in arrays:-

It is proved that the binary heap is a Complete Binary Tree, which demonstrates the No.of arrays.

extractMin(): It is a function mainly used for the extracting the min-value from the nodes and traverse the result into the respective array.

Algorithm:-

Finally, The runtime for 'Big 0 notation for binary heap is "0(n)"

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.