212
правок
Изменения
м
→Уменьшение последовательности куч путём удаления элемента справа
=== Уменьшение последовательности куч путём удаления элемента справа ===
Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. что корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>.
