3622
правки
Изменения
м
swap(x <tex>\leftrightarrow</tex> , y)
swap(x.L <tex>\leftrightarrow</tex> , x.R)
Нет описания правки
Слияние двух куч.
'''merge'''(x, y) : // x, y {{---}} корни двух деревьев
'''if''' x == <tex> \varnothing </tex>: '''return''' y
'''if''' y == <tex> \varnothing </tex>: '''return''' x
'''if''' y.key < x.key:
// Воспользуемся тем, что куча левосторонняя. Правая ветка {{---}} самая короткая и не длиннее логарифма.
// Пойдем направо и сольем правое поддерево с у.
// Могло возникнуть нарушение левостороннести кучи.
'''if''' dist(x.R) > dist(x.L):
dist(x) = min(dist(x.L), dist(x.R)) + 1 // пересчитаем расстояние до ближайшей свободной позиции
'''return''' x
