Изменения

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

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

1148 байт добавлено, 00:17, 31 мая 2015
Нет описания правки
</code>
=== Конфлюэнтная персистентность Персистентность ===Так как Биноминальная куча можно сделать [[Персистентные структуры данных|персистентной]] при реализации на списках. Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Это возможно благодаря тому, что нигде не делается уничтожающих присваиваний и не создается новых узлов в <tex>\mathrm{merge}, а также поддержке самой операции <math/tex>. Также поддерживается операция <tex>\mathrm {merge}</mathtex> биномиальная куча является конфлюэнтной структурой данныхдля всех версий биномиальных куч, что позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности. Персистентная биноминальная куча используется для [[Персистентная приоритетная очередь|персистентной приоритетной очереди]].
251
правка

Навигация