The following I said is to start from the root node and adjust down one by one 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). In the concept of the textbook, we should remove the coefficient, so A and B have the same time complexity. However, in practical applications, smart people will choose A, after all, the time complexity of A is lower except for a 2 in n.
So in order to calculate more clearly, the process of calculating time complexity will be more detailed.
First, start from the root node and adjust down one by one, 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 adjusting down, 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 down 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 down 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 adjusting down, 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 starting from the last non-leaf node and adjusting down one by one and starting from the root node and adjusting down one by one is both 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.