The following I said, starting from the root node, each one is adjusted downward without traversing the leaf nodes.
Due to the concept of time complexity, it is actually unclear when comparing the time complexity of two objects. For example, the time complexity of A is O(n/2), and the time complexity of B is O(n). According to the concept in the textbook, we should remove the coefficient, so A and B have the same time complexity. However, in practical applications, no one would choose B, after all, the time complexity in A is lower except for a 2.
So in order to calculate more clearly, the process of calculating time complexity will be more detailed.
First, starting from the root node, each one is adjusted downward, and it is necessary to traverse each non-leaf node in the array. If there are n nodes, then there are n/2 non-leaf nodes, so the time complexity is O(n/2).
Next, in the process of downward adjustment, each node needs to sink at least and at most to the depth of the tree, which is logn. Therefore, the time complexity of each node sinking is O(logn/2).
Therefore, the total time complexity of starting from the root node and adjusting downward one by one is O((n/2)*(logn/2)).
Next, let's calculate the time complexity of starting from the last non-leaf node and adjusting downward one by one. Similarly, the number of non-leaf nodes is still n/2, and the time complexity is O(n/2).
Next, in the process of downward adjustment, each node needs to sink at least and at most to the depth of the tree, which is logn.
Therefore, the time complexity of each node sinking is also O((n/2)*(logn/2)).
In fact, the time complexity of adjusting downward one by one from the last non-leaf node and from the root node is simplified to O(nlogn). Therefore, in terms of time complexity, they are not fundamentally different.
The above are some thoughts and insights that I had while reading, which may not be correct. Readers are welcome to discuss! Let's learn and progress together.