3622
правки
Изменения
м
→Вставка элемента
#* Пока размер текущей кучи больше <tex dpi = 120> 1 </tex>, и значение корня любой из куч-потомков больше значения корня текущей кучи:
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
Просеивание в куче Леонардо сильно упрощено, так как каждая куча либо будет одноэлементной, иметь либо будет иметь двух потомков, либо ноль. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:
