Левосторонняя куча
Определение
Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое название они получили из-за того, что левое поддерево обычно длиннее правого.
| Определение: |
| Левосторонняя куча (leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи (heap order). |
| Лемма (1): |
В двоичном дереве с n вершинами существует свободная позиция на глубине не более logn. |
| Доказательство: |
| Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более n. |
Левосторонняя куча накладывает на двоичное дерево дополнительное условие. Ближайшая свободная позиция должна быть самой правой позицией в дереве. То есть помимо условия кучи выполняется следующее:
| Определение: |
| Условие левосторонней кучи. Пусть dist(х) – расстояние от вершины u до ближайшей свободной позиции в ее поддереве. У пустых позиций dist = 0. Тогда потребуем для любой вершины х: dist(x.L)>= dict(x.R). |
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за О(1) поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
Поддерживаемые операции
merge
Слияние двух куч.
merge(x,y) //x,y – корни двух деревьев
if x == NULL return y
if y == NULL return x
if y.key < x.key :
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;
//Каждый раз идет в уже существующей вершине только в правое поддерево — не более логарифма вызовов (по лемме).
Левосторонняя куча относится к сливаемым кучам: остальные операции легко реализуются с помощью операции слияния.
insert
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
extractMin
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
delete
Аналогично удаляется любой элемент — на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя — на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью decrease key. Уменьшаем ключ до -inf, затем извлекаем минимальное значение.
decKey
| Лемма (2): |
У левостороннего дерева с правой ветвью длинны h количество узлов n>= 2^h – 1. |
| Доказательство: |
|
Индукция по h. При h = 1 – верно. При h > 1 левое и правое поддеревья исходного дерева левосторонние, а dist от их корней >= h – 1. По индукции число узлов в каждом из них >=2^(h - 1) – 1, тогда во все дереве n >= (2^(h – 1) – 1) + (2^(h – 1) – 1) +1 = 2^h – 1 узлов. |
Алгоритм
1. Найдем узел х, вырежем поддерево с корнем в этом узле. 2. Пройдем от предка вырезанной вершины, при этом пересчитывая dist. Если dist левого сына вершины меньше dist правого, то меняем местами поддеревья.
| Лемма (3): |
Нужно транспонировать не более logn поддеревьев. |
| Доказательство: |
| Длина пути от вершины до корня может быть и O(n), но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если dist(x.L) < dist(x.R), но dist(x.R) <= logn. На каждом шаге, если нужно транспонируем и увеличиваем dist++, тогда dist увеличится до logn и обменов уже не надо будет делать. |
Таким образом, мы восстановили левостороннесть кучи за O(logn) 3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. O(logn)
Построение кучи за О(n)
Храним список левосторонних куч. Пока их количество больше >1, из начала списка достаем две кучи, сливаем их и кладем в конец списка.
Преимущества левосторонней кучи
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в merge. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация merge является персистентной.
