Изменения

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

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

15 байт убрано, 16:52, 7 июня 2012
Нет описания правки
=== getMinimum ===
[[Файл:binHeapExample1_1.png|right|300px]]
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом <tex>1</tex>.
[[Файл:binHeapExample1_1.png|300px]]
=== merge ===
[[Файл:binHeapExample2_5.png|right|600px|Пример слияние двух деревьев одинакового порядка]]
 
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log(n))</tex>.
[[Файл:binHeapExample2_5.png|600px|Пример слияние двух деревьев одинакового порядка]]
<code>
Node merge(H1, H2) {
333
правки

Навигация