4 votes 4 votes If you are given a sorted list with n elements in ascending order. Then what will be the Time complexity to build a Min heap from the given array? DS data-structures binary-heap time-complexity + – Gaurab Ghosh asked Jan 18, 2017 • recategorized Jul 7, 2022 by Lakshman Bhaiya Gaurab Ghosh 1.5k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Samujjal Das commented Jan 18, 2017 reply Follow Share O(1) i guess because array is already following min heap property. 0 votes 0 votes Gaurab Ghosh commented Jan 18, 2017 reply Follow Share But to know that the array is following min heap property; don't we need at least one pass of the entire array? Just to make sure it is following min heap property. This is my doubt. 0 votes 0 votes Samujjal Das commented Jan 18, 2017 reply Follow Share It is already given that the array is in ascending order right? So, already if a node is at index 'i', then its left child is at '2i' and right child is at '2i+1'. 0 votes 0 votes srestha commented Jan 18, 2017 reply Follow Share It will take O(n) time, as we have to simply call build heap method 0 votes 0 votes Rahul Jain25 commented Jan 18, 2017 reply Follow Share We dont need to call any method. It is sorted in ascending then it is definately min heap right?? 0 votes 0 votes srestha commented Jan 18, 2017 reply Follow Share But the question is "Time complexity to build a Min heap from the given array" 0 votes 0 votes Rahul Jain25 commented Jan 18, 2017 reply Follow Share I think build heap means just set correct elements at correct positions. And if we know list is sorted in ascending, then do we need to call build heap??? I think O(1) should hold. 0 votes 0 votes Gaurab Ghosh commented Jan 18, 2017 reply Follow Share Yes srestha To know that the given array satisfies the min heap condition, we need to check the entire array once. Right? 0 votes 0 votes srestha commented Jan 18, 2017 reply Follow Share yes We have given an array in ascending order Now, we have to build min heap We cannot do this less than O(N) time 0 votes 0 votes Vijay Thakur commented Feb 4, 2017 reply Follow Share Answer should be O(1) as it's said that we have been given a sorted array. No need to check. 0 votes 0 votes Tesla_fan commented Aug 26, 2017 reply Follow Share Even if we give input as sorted,how could a system wouldld check if the list is sorted or not so it's taking o(n). 0 votes 0 votes smsubham commented Dec 27, 2017 reply Follow Share @srestha If we are given that it is already sorted in descending order and in array form. isn't it already a min heap? Why do we need to check or call build heap? 0 votes 0 votes vamp_vaibhav commented Dec 27, 2017 reply Follow Share Isn't the question like.. You have given an array in ascending order.. What is the time complexity to check whether it is sorted or not? 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes see this http://www.geeksforgeeks.org/g-fact-85/ Bikram answered Jan 18, 2017 Bikram comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 27, 2017 reply Follow Share If we are given that it is already sorted in descending order and in array form. isn't it already a min heap? Why do we need to check using heapify or call build heap? 0 votes 0 votes Please log in or register to add a comment.