Изменения

x<-> y //Воспользуемся тем, что куча левосторонняя. Правая ветка — самая короткая и не длиннее //логарифма. Пойдем направо и сольем правое поддерево с у. x.R<-merge(x.R, y) //Могло возникнуть нарушение левостороннести кучи. If dist(x.R) > dist(x.L): x.L<->x.R update dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1 return x; //Каждый раз идет в уже существующей вершине только в правое поддерево — не более логарифма вызовов (по лемме).

Так как левосторонняя Левосторонняя куча относится к сливаемым кучам, : остальные операции легко реализуются с помощью операции слияния.