As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness.
Firstly, I define the following procedure (pseudocode):
process_node(): if the node has children: select the child node with the maximum value if the selected node's value is greater than the value of current node: swap current node with the selected node
Then I run this procedure on all non-leaf nodes going down level by level in the binary tree view of the array. So the root is processed first, then comes the first level etc. After doing this, a half of leaf nodes become smaller than all of their ancestors. Another run of the procedure on the same nodes settles the other half of the leaves. Thus, they have been put in place in the heap and can be removed from the processing.
The number of leaves is halved, and so is the number of non-leaf nodes. The procedure is run again on new non-leaves, and the process is repeated until all the elements of the array are processed.
The number of nodes on which the procedure is run starts with $N/2$ and later is halved. We get a decreasing geometric series with the sum being $O(N)$.
Are there any mistakes in my reasoning?
An example with 7 elements. The number of levels $L = 3$.
1 / \ 2 3 / \ / \ 4 5 6 7
Step 1. The root node is processed with
3 / \ 2 1 / \ / \ 4 5 6 7
Step 2. The nodes in the level 1 are processed. The total number of levels processed in this way is $L' = L - 1$.
3 / \ 5 7 / \ / \ 4 2 6 1
The processing of each node sifts the smallest value in the node and its direct descendants one level down. Each node thus "generates" the smallest value for its children. After steps 1 and 2 are completed, the values "2" and "1" are on their correct places. It is a half of the leaf nodes.
Step 3. Repeat steps 1 and 2. The lowest level is completely filled and can be excluded from further processing. The second lowest level can be thought of as the new "leaves".
7 / \ 5 6 / \ / \ 4 2 3 1
The heap is now fully built, but it seems to be an accident that it is constructed this early. So,
Step 4. Do steps 1 and 2 for the first $L' = L' - 1$ levels. Repeat until $L' = 0$.