It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ?The argument here is, If my input has all the same keys, then every time I delete the root, I do not need to heapify, I just need to swap with the rightmost leaf.Why is the above argument not valid ?
Heap sort best case time - $\mathcal O(n)$?
algorithms;algorithm analysis;sorting;heaps;heap sort