TIFR CSE 2011 | Part B | Question: 21

Question

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?

• A. This problem can be solved in $O(\log n)$ time.
• B. This problem can be solved in $O (n)$ time but not in $O(\log n)$ time.
• C. This problem can be solved in $O(n\log n)$ time but not in $O (n)$ time.
• D. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time.
• E. None of the above.

Answer 1

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

Comments

Option c correct ???

---

No. because it says not in $O(n)$.

---

Arjun sir please explain this problem ,it just not hitting to me

---

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.

---

@Arjun

sir, isn't it indirectly saying HEAP SORT ?

---

No. It only implies create heap.

---

sorry sir, i misread the term storing as sorting.

---

What will be the time taken to insert elements in the array maintain the given heap property?

Answer 2

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 )

Comments

NO need of balancing [ O(logn) ] , just Build_min_heap [ O(n) ] , that’s all !