Изменения

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

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

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

Навигация