Изменения

Перейти к: навигация, поиск

Двоичная куча

1 байт убрано, 22:25, 18 марта 2012
Восстановление свойств кучи
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Downsift_down''' (просеивание вниз) и '''Sift_Upsift_up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Downsift_down(i)'''.Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Downsift_down()''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.
If (min <> i)
Поменять A[i] и A[minimum]
Sift_Downsift_down(min)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией '''Sift_Upsift_up(i)'''.
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Sift_Upsift_up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
Sift_Upsift_up(i / 2)
</code>
72
правки

Навигация