edited by
1,404 views
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)
edited by

2 Answers

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

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
0 answers
2
6 votes
6 votes
2 answers
3
Vishal Goyal asked Dec 6, 2016
729 views
The number of min heap trees are possible with 15 elements such that every leaf node must be greater than all non-leaf nodes of the tree are ________.
5 votes
5 votes
2 answers
4
Utkarsh Joshi asked Nov 24, 2018
3,439 views
The minimum number of comparisons required to find the 65th smallest element in a minheap is equal to