GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
70 views

Consider a complete Binary Tree ‘T’ with key of root node be ‘P’. It is given that the left and right subtree of ‘P’ satisfies min-heap property. What is the time taken to convert the given tree ‘T’ to a max heap ?

a)O(log N)

b) O(N)

asked in DS by Veteran (54.7k points)   | 70 views

Apply Build_Max_Heap procedure on the tree, which takes O(N) time.

if the question is

Consider a complete Binary Tree ‘T’ with key of root node be ‘P’. It is given that the left and right subtree of ‘P’ satisfies min-heap property. What is the time taken to convert the given tree ‘T’ to a min heap ?

 

then answer should be log N, rt?

@Sreshtha
yes, then answer will be log(n), call min-heapify function on root which takes logn time
thank u :)

1 Answer

+1 vote

The answer should be O(N)  as we need to to heapify all the nodes in botton up fashion.

answered by (325 points)  

Related questions

+1 vote
1 answer
2
asked in DS by srestha Veteran (54.7k points)   | 73 views
0 votes
0 answers
3
asked in DS by vaishali jhalani Boss (6k points)   | 35 views


Top Users Jun 2017
  1. Bikram

    2802 Points

  2. Hemant Parihar

    1480 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1334 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1180 Points

  7. rahul sharma 5

    1072 Points

  8. Debashish Deka

    894 Points

  9. Arjun

    868 Points

  10. srestha

    848 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Niraj Singh 2

    1306 Points

  2. Bikram

    1058 Points

  3. junaid ahmad

    502 Points

  4. Rupendra Choudhary

    292 Points

  5. just_bhavana

    266 Points


23,333 questions
30,018 answers
67,234 comments
28,344 users