MadeEasy Test Series: Algorithms - Heap

Question

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)

Comments

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)

---

I also think answer should be 0(nlogn).  @santhoshdevulapally

Answer 1

We have 2n number of elements and building a min heap using 2n elemets take O(2n) i.e.O(n) time

Comments

ypu call build heap which is O(n)
and then min heapify which is O(logn)
therefore O(nlogn) right?

---

@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..

---

got it :)

Answer 2

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.

Comments

your approach is wrong, in max heap not necessary that last element should be minimum.