Открыть список
Как стать автором
Обновить

Комментарии 4

Для более простого объяснения алгоритм достаточно назвать «царь горы». Это более наглядное название происходящего.

Построение пирамиды — O(N) по времени. Почему так? На самом деле формирование кучи можно описать по другому. Мы идем с середины массива, и делаем просеивания для элементов на уровнях, без рекурсивного вызова. Допустим для упрощения, длина массива N = 2^n — 1, пирамида ровненькая. Просеивания для нижнего уровня нелистовых элементов — высотой 1, таких элементов N/4. Для уровня выше высота будет 2, там N/8 элементов, потом 3 и N/16 элементов, и т.д. Если это дело просуммировать, то получаем O(N)

Вы абсолютно правы!
Я опишу этот вариант в статье.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
Местоположение
Россия
Сайт
otus.ru
Численность
51–100 человек
Дата регистрации
Представитель
OTUS

Блог на Хабре