GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
62 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 Junior (819 points)   | 62 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 (271 points)  

Related questions

0 votes
0 answers
2
asked in DS by Vishal Goyal Junior (819 points)   | 39 views
0 votes
0 answers
3
asked in DS by Vishal Goyal Junior (819 points)   | 39 views
Top Users Feb 2017
  1. Arjun

    5396 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,023 answers
59,698 comments
22,136 users