GATE IT 2004 | Question: 53

Question

An array of integers of size $n$ can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node $\left \lfloor (n - 1) /2 \right \rfloor$, and doing this adjustment up to the root node (root node is at index $0$) in the order $\left \lfloor (n - 1) /2 \right \rfloor$, $\left \lfloor (n - 3) /2 \right \rfloor$, ....., $0$. The time required to construct a heap in this manner is

• A. $O(\log n)$
• B. $O(n)$
• C. $O (n \log \log n)$
• D. $O(n \log n)$

Comments

Can I say the reason it is not O(nlogn) is coz we don't know what type of heap we are creating is it a max heap or min heap. So we just assume that we are building a heap using build heap method which take linear time?
And if we are building a heap using build heap method why we are not calling max heapify to maintain the heap property??

---

@vupadhayayx86 build heap means constructing min-heap or max-heap and heapify function is called. You can check the proof in cormen for why the time complexity is O(n)

---

Building a HEAP taken O(n) time and to max/min heapify, it takes O(log n) time
So O(n + log n) = O(n).

---

@34:48

https://www.youtube.com/watch?v=B7hVxCmfPtM 

---

It’s the standard definition of Build Heap where we heapify the array elements from A[n/2] to A[1]  (array index starts from 1).

Answer 1

By using Build Heap method we can create heap from complete binary tree.

which will take $O(n)$.

Correct Answer: $B$

Comments

Youtube

---

can't believe GATE can sometimes ask so trivial question !!!!!!!!!!!!!

---

@s_dr_13
Those who have not read from standard sources will think it like this way-
max_heapify takes O(lg n) and there are n/2 elements  so build heap will take O(nlgn).

Answer 2

The above statement is actually algorithm for building a Heap of an input array A.

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Upper bound of time complexity is O(n) for above algo

Comments

Refer:

https://www.geeksforgeeks.org/gate-gate-it-2004-question-53/

---

For understanding refer:

https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/

Answer 3

Well, there are two methods fro constructing a heap:

1. Entering key into the heap one by one: O(nlogn)

2. Building heap from an array: O(n)

I will not discuss the entire method here, but I will mention the technique.

When we construct heap from an array we do not actually construct any tree. We create a heap by simply doing certain adjustment in the position in the array so that it behaves like a heap.

Specifically speaking, the relation is that for every parent node,  its child nodes will be at index (2i+1, 2i+2) where i=0,1,2.....

Now we know that number of leaf nodes the heap would (n+1)/2. So here we do nothing to the leaf nodes.

We simple perform adjustments on the remaining floor(n/2) elements.

The adjustment includes:

2 comparisons with the child node

And​ atmost 1 swap if required.

hence, overall time complexity is O(1)

So for adjusting, n/2 elements, it will take O(n) time.

This question has the description of constructing a heap from an array.

Hence, the answer would be O(n).

Answer 4

B

By using BUILD-HEAP Method

takes O(n) time.