72
правки
Изменения
→Восстановление свойств кучи
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Down''' (просеивание вниз) и '''Sift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Down()''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.
