Почему heapSort работает за n log N?

Question

[UID_B Nintendo]

У меня есть куча её высота log n. Я её хочу отсортировать, n - это случаем не количество вершин которые надо отсортировать ?

Answer 1

[Владимир Олохтонов]

N – это число элементов в куче, при сортировке вам нужно поочередно достать из кучи все элементы, после каждого извлечения кучу надо перестроить, это требует O(logN) операций.

Всего получается O(NlogN).