Карточка Senior Куча обновлено
Построение кучи за O(n)
Вопрос
За сколько можно построить кучу из готового массива и как?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
За O(n): просеивание вниз от последнего родителя (n 1) - 1 к корню. Большинство узлов низко и просеиваются на малую высоту, сумма работ сходится к O(n).
Ответ
За O(n): просеивание вниз от последнего родителя (n >> 1) - 1 к корню. Большинство узлов низко и просеиваются на малую высоту, сумма работ сходится к O(n). Вставка по одному даёт O(n log n).
Разбор
За O(n): просеивание вниз от последнего родителя (n >> 1) - 1 к корню. Большинство узлов низко и просеиваются на малую высоту, сумма работ сходится к O(n). Вставка по одному даёт O(n log n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.