212
правок
Изменения
м
Так как в последовательности <tex dpi = 120> O(\log{N}) </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>.
→Восстановление свойств последовательности
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
siftDown(i)
</code>
Так как в последовательности <tex dpi = 120> O(\log{N}) </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>.
=== Уменьшение последовательности куч путём удаления элемента справа ===
