imagine such a scenario. If all the elements in the heap are the same, then every time the heap is adjusted, there is no need to adjust the heap after the exchange of the top element and the tail element, and then the n elements will do so. Isn"t this sort time complexity O (n)
?https://en.wikipedia.org/wiki.
is n, don't put too much faith in those online blog posts, in addition, different code may also lead to nlogn. Wikipedia, for example, also says nlogn (n, wrong).
https://zh.wikipedia.org/zh/%.
just saves the time of adjustment, and the number of comparisons between elements is still nlgn
.