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?