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?
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)$.
@Arjun
sir, isn't it indirectly saying HEAP SORT ?
64.3k questions
77.9k answers
244k comments
80.0k users