(a) A valid binomial min heap A contains n items. A further n items are held in
ID: 3826357 • Letter: #
Question
(a) 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. (b) 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) Time Complexity = O(nlogn)
1. A min heap is a specialized tree with property parant element is always less value than chailds .
2 .Finally root have min element .
3 .This min element is removed from heap and placed in arbitary array .
4.Construct now min heap after removing root element .(Constructing min each time takes logn time)
5.Repeat stepe 2-5 ,the above process untill no element untill heap (This process is performed n times)
6.Finally run time =O(nlogn)
b) Run time =O(2nlog2n) =O(nlog2n) ,Because you are performing heap on 2n elements.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.