Изменения
→merge
if y == NULL return x
if y.key < x.key :
x<-tex>\leftrightarrow</tex>y
//Воспользуемся тем, что куча левосторонняя. Правая ветка — самая короткая и не длиннее
//логарифма. Пойдем направо и сольем правое поддерево с у.
x.R<-tex>\leftarrow</tex> merge(x.R, y)
//Могло возникнуть нарушение левостороннести кучи.
If dist(x.R) > dist(x.L):
x.L<-tex>\leftrightarrow</tex>x.R
update dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1
return x;
Левосторонняя куча относится к сливаемым кучам: остальные операции легко реализуются с помощью операции слияния.
===insert===
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
