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