Изменения

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

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

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

Навигация