17 votes 17 votes Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ such that the following min-heap property is maintained for all $2\leq i\leq n: A [\lfloor i/2\rfloor]\leq A[i]$. (Note that $\lfloor x\rfloor$ is the largest integer that is at most $x$). Which of the following statements is TRUE? This problem can be solved in $O(\log n)$ time. This problem can be solved in $O (n)$ time but not in $O(\log n)$ time. This problem can be solved in $O(n\log n)$ time but not in $O (n)$ time. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time. None of the above. Algorithms tifr2011 algorithms sorting + – makhdoom ghaya asked Oct 20, 2015 • edited May 14, 2018 by Milicevic3306 makhdoom ghaya 2.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 27 votes 27 votes Store the elements in an array and then call build_heap(A). the build_heap takes $O(n)$ time. So, option 'b' is correct. But, if we try building heap by inserting each element one by one, the total complexity will be then $O(n \log n)$. Because insertion takes $O(\log n)$ and inserting '$n$' elements will take $O(n \log n)$. Sujit Kumar Muduli answered Oct 20, 2015 • edited Nov 15, 2017 by kenzou Sujit Kumar Muduli comment Share Follow See all 8 Comments See all 8 8 Comments reply tamil93 commented Jan 20, 2016 reply Follow Share Option c correct ??? 0 votes 0 votes Arjun commented Jan 20, 2016 reply Follow Share No. because it says not in $O(n)$. 7 votes 7 votes talha hashim commented Jun 27, 2018 reply Follow Share Arjun sir please explain this problem ,it just not hitting to me 0 votes 0 votes Anshul999 commented Jun 23, 2019 reply Follow Share I think the answer should be "C", because to build a heap from the given n elements it takes O(n) and then we have to apply min heapify to satisfy the min-heap property which takes O(log n) so the overall complexity will be O(n log n) but not in O(n) time. @Arjun Sir please correct me if I am wrong. 0 votes 0 votes Shaik Masthan commented Jun 23, 2019 reply Follow Share @Arjun sir, isn't it indirectly saying HEAP SORT ? 0 votes 0 votes Arjun commented Jun 23, 2019 reply Follow Share No. It only implies create heap. 4 votes 4 votes Shaik Masthan commented Jun 24, 2019 reply Follow Share sorry sir, i misread the term storing as sorting. 1 votes 1 votes pranavsettaluri9 commented Jul 1, 2020 reply Follow Share What will be the time taken to insert elements in the array maintain the given heap property? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes As per the given question statement,we can take all the n numbers and build a min-heap in O(n) time. For maintaining the min-heap property, we will do balancing in O(log n) time. Hence total time =O (n +log n). =O(n ) sutanay3 answered Aug 1, 2018 sutanay3 comment Share Follow See 1 comment See all 1 1 comment reply Hareesh22 commented Sep 14, 2020 reply Follow Share NO need of balancing [ O(logn) ] , just Build_min_heap [ O(n) ] , that’s all ! 0 votes 0 votes Please log in or register to add a comment.