3 votes 3 votes Consider M1 and M2 be two complete binary tree which satisfy max-heap property, each of size ‘n’. What is the time complexity to combine both M1 and M2 such that combine tree will be min heap tree? O (n log n) O (n) O (n2) O (n2 log n) DS made-easy-test-series data-structures binary-heap time-complexity + – Vishal Goyal asked Dec 6, 2016 edited Mar 4, 2019 by akash.dinkar12 Vishal Goyal 1.4k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply santhoshdevulapally commented Dec 6, 2016 reply Follow Share M1 and M2 are contain total of 2n elements.(stores it in the array and construct min heap) to construct min heap with n elements is o(nlogn) =o(2nlog2n)=o(nlogn) 0 votes 0 votes rish1602 commented Jul 22, 2021 reply Follow Share I also think answer should be 0(nlogn). @santhoshdevulapally 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes We have 2n number of elements and building a min heap using 2n elemets take O(2n) i.e.O(n) time Prateek Yadav 2 answered Dec 6, 2016 Prateek Yadav 2 comment Share Follow See all 3 Comments See all 3 3 Comments reply A_i_$_h commented Aug 19, 2017 reply Follow Share ypu call build heap which is O(n) and then min heapify which is O(logn) therefore O(nlogn) right? 0 votes 0 votes joshi_nitish commented Aug 19, 2017 reply Follow Share @A_i_$_h it will be O(n) only in build heap procedure only, it will be converted to heap, then why call min heapify.. 0 votes 0 votes A_i_$_h commented Aug 22, 2017 reply Follow Share got it :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Since it is given that the tree satisfy max heap.So just the reverse array element and copy it in size of 2n array.Then it would be a min heap. rahul_vicky answered Nov 30, 2019 rahul_vicky comment Share Follow See 1 comment See all 1 1 comment reply Devwritt commented Jun 11, 2020 reply Follow Share your approach is wrong, in max heap not necessary that last element should be minimum. 0 votes 0 votes Please log in or register to add a comment.