edited by
2,053 views
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?

  1. This problem can be solved in $O(\log n)$ time.
  2. This problem can be solved in $O (n)$ time but not in $O(\log n)$ time.
  3. This problem can be solved in $O(n\log n)$ time but not in $O (n)$ time.
  4. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time.
  5. None of the above.
edited by

2 Answers

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)$.

edited by
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 )
Answer:

Related questions

39 votes
39 votes
4 answers
2