143
правки
Изменения
→Сложность
== Сложность ==
Операция <tex> \mathrm{siftDown} </tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.
Достоинства:
* Худшее время работы {{---}} <tex>O(n\log(n))</tex>.
* Требует <tex>O(1)</tex> дополнительной памяти.
Недостатки:
* Неустойчивая
* Неэффективное использование кэша, так как наше движение по массиву в чем-то похоже на хаотичное.
* На почти отсортированных данных работает столь же долго, как и на хаотических данных.
== Пример ==
