The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
139 views

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)
asked in DS by Active (2.2k points)
retagged by | 139 views
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)

1 Answer

+2 votes
We have 2n number of elements and building a min heap using 2n elemets take O(2n) i.e.O(n) time
answered by (313 points)
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 :)

Related questions

0 votes
0 answers
2
asked in DS by Vishal Goyal Active (2.2k points) | 58 views
0 votes
0 answers
3
asked in DS by Vishal Goyal Active (2.2k points) | 51 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,834 questions
36,689 answers
90,626 comments
34,641 users