1 votes 1 votes 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) DS time-complexity + – srestha asked Jan 4, 2017 srestha 570 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Uzumaki Naruto commented Jan 4, 2017 reply Follow Share Apply Build_Max_Heap procedure on the tree, which takes O(N) time. 2 votes 2 votes srestha commented Jan 4, 2017 reply Follow Share 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? 0 votes 0 votes Vijay Thakur commented Jan 4, 2017 reply Follow Share @Sreshtha yes, then answer will be log(n), call min-heapify function on root which takes logn time 2 votes 2 votes srestha commented Jan 4, 2017 reply Follow Share thank u :) 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes The answer should be O(N) as we need to to heapify all the nodes in botton up fashion. Abhijit Borah answered Jan 8, 2017 Abhijit Borah comment Share Follow See all 0 reply Please log in or register to add a comment.