Изменения

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

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

72 байта убрано, 23:01, 15 июня 2014
Восстановление свойств кучи
<code>
'''function''' siftDown(i : '''int'''):
'''ifwhile''' 2 * i + 1 2 <= Aa.heap_size <font color = "green">// <tex>heap</tex>_<tex>size </tex> {{---}} количество элементов в куче</font> '''if''' 2 * i + 1 <= a.heap_size left = A[2 * i + 1] <font color = "green">// левый сын</font> '''else''' left = inf '''if''' 2 * i + 2 <= A.heap_size
right = A[2 * i + 2] <font color = "green">// правый сын</font>
'''else''' right = inf '''if''' left == right == inf '''return''' '''if''' right <= left '''and''' right < A[i] swap(A[2 * i + 2], A[i]) siftDown( i = 2 * i + 2) '''ifelse''' left < A[i] swap(A[2 * i + 1], A[i]) siftDown( i = 2 * i + 1)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
333
правки

Навигация