1302
правки
Изменения
Нет описания правки
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Shift_DownSift_Down''' (просеивание вниз) и '''Shift_UpSift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Shift_DownSift_Down(i)'''.Работа процедуры : если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Shift_DownSift_Down(i)''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.
<code>
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
If (min <> i)
Поменять A[i] и A[minimum]
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией'''Shift_UpSift_Up(i)'''.
Работа процедуры : если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Shift_UpSift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.
<code>
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
</code>
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Shift_DownSift_Down(i)''' для корня.
# Сохранённый элемент возвращается.
<code>
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
return min
</code>
A.heap_size = A.heap_size + 1
A[A.heap_size] = key
</code>
== Источники ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча]
