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