Изменения

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

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

Нет изменений в размере, 15:17, 10 марта 2012
merge
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
[[Файл:binHeapExample2_2binHeapExample2_3.png|thumb|500px|Пример слияние двух деревьев одинакового порядка]]
Вот в чем состоит ее суть: пусть есть две биномиальные кучи с <tex>H</tex> и <tex>H'</tex>. Размеры деревьев в кучах соответствуют двоичным числам <tex>m</tex> и <tex>n</tex>, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев <tex>B_{k-1}</tex> в дерево <tex>B_{k}</tex>. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним(пример работы этого действия приведен на рисунке справа).
333
правки

Навигация