edited by
10,595 views
51 votes
51 votes

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

  1. $O(\log n)$
  2. $O(n)$
  3. $O (n \log \log n)$
  4. $O(n \log n)$
edited by

4 Answers

Best answer
50 votes
50 votes

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

which will take $O(n)$.

Correct Answer: $B$

edited by
17 votes
17 votes

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

5 votes
5 votes

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:

Related questions

24 votes
24 votes
1 answer
1
65 votes
65 votes
9 answers
2
Ishrat Jahan asked Nov 1, 2014
24,559 views
Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to del...
23 votes
23 votes
4 answers
3
Ishrat Jahan asked Nov 2, 2014
4,857 views
Which one of the following binary trees has its inorder and preorder traversals as $BCAD$ and $ABCD$, respectively?