Изменения

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

Биномиальная куча

454 байта добавлено, 13:21, 10 марта 2012
decreaseKey
=== decreaseKey ===
Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх, то есть алгоритм состоит в том, что текущий элемент, в случае его минимальности относительно его родителя, будет на каждом шаге меняться с этим родителем, и указатель на текущую вершину будет изменен соответственно на родителя, с которым поменяли. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку глубина вершины <tex>x</tex> есть <tex>O(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх. 
<code>
333
правки

Навигация