Когда все элементы равны, куча делает O (n) шагов. Потому что, когда элемент добавляется в кучу после сравнения O (1), мы видим, что он находится в правильном положении.
Удаление корня также является O (1), когда мы меняем хвост и корень, свойство кучи все еще выполняется.
Все элементы добавляются в кучу в O (n) и удаляются в O (n). Итак, да в этом случае heapsort равен O (n). Я не могу придумать лучшего варианта, поэтому лучшим вариантом для heapsorts должно быть O (n).
«Наилучшим случаем Heapsorts является O (n)» означает на английском языке что-то вроде: существуют массивы размера n, так что для сортировки heapsort требуется не более k * n. Это хорошо в теории, но на практике это не говорит о том, насколько хорош или быстрый порт.