Изменения

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

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

53 байта добавлено, 18:14, 6 июня 2012
→‎Восстановление свойств кучи
<code>
sift_down(i)
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
// heap_size - количество элементов в куче
if (left 2 * i <= A.heap_size) and (A[ left] < = A[2 * i]) min = left// левый сын
else
min left = iinf If if (right 2 * i + 1 <= A.heap_size) and (A[ right] < = A[2 * i+ 1]) min = right// правый сын
else
min right = iinf if (left == right == inf) return if (min right <> = left && right < A[i]) swap(2 * i + 1, i) Поменять sift_down(2 * i + 1) if (left < A[i] и A[minimum]) swap(2 * i, i) sift_down(min2 * i)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией sift_up(i).
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/24117»

Навигация