Изменения
→Операции над биномиальными кучами
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log(n))</tex>.
<code>
Node merge(H1, H2) {
if (H1 == null) {
return H2;
}
if (H2 == null) {
return H1;
}
// H - результат слияния
H.head = null;
// Слияние корневых списков
curH = H.head;
curH1 = H1.head;
curH2 = H2.head;
while curH1 != null && curH2 != null {
if (curH1.degree < curH2.degree) {
curH.sibling = curH1;
curH = curH1;
curH1 = curH1.sibling;
} else {
curH.sibling = curH2;
curH = curH2;
curH2 = curH2.sibling;
}
}
if (curH1 == null) {
while curH2 != null {
curH.sibling = curH2;
curH2 = curH2.sibling;
}
} else {
while curH1 != null {
curH.sibling = curH1;
curH1 = curH1.sibling;
}
}
// объединение деревьев одной степени
curH = H.head;
while curH.sibling != null {
if curH.degree == curH.sibling.degree {
p[curH] = curH.sibling;
tmp = curH.sibling;
curH.sibling = curH.sibling.child;
curH = tmp;
continue;
}
curH = curH.sibling;
}
return H;
}
</code>
=== insert ===
