212
правок
Изменения
м
→Вставка элемента
После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]] (см. ниже псевдокод):
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
# Пока слева от неё есть куча , и значение её корня больше значения текущего корня и обоих корней куч-потомков:
#* Меняются местами новый корень и корень кучи слева (что не нарушит свойство для текущей кучи). Эта куча становится текущей.
# Выполняется «просеивание», чтобы выполнялось свойство кучи:
#* Пока размер текущей кучи больше <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}) + O(\log{N}) = O(\log{N}) </tex>.
