Левосторонняя куча

Определение

Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое название они получили из-за того, что левое поддерево обычно длиннее правого.

Определение:

Левосторонняя куча (leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи (heap order).

Лемма (1):

В двоичном дереве с n вершинами существует свободная позиция на глубине не более logn.

Доказательство:

[math]\triangleright[/math]

Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более n.

[math]\triangleleft[/math]

Левосторонняя куча накладывает на двоичное дерево дополнительное условие. Ближайшая свободная позиция должна быть самой правой позицией в дереве. То есть помимо условия кучи выполняется следующее:

Определение:

Условие левосторонней кучи. Пусть 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.

Доказательство:

[math]\triangleright[/math]

Индукция по 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 узлов.

[math]\triangleleft[/math]

Алгоритм

1. Найдем узел х, вырежем поддерево с корнем в этом узле. 2. Пройдем от предка вырезанной вершины, при этом пересчитывая dist. Если dist левого сына вершины меньше dist правого, то меняем местами поддеревья.

Лемма (3):

Нужно транспонировать не более logn поддеревьев.

Доказательство:

[math]\triangleright[/math]

Длина пути от вершины до корня может быть и O(n), но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если dist(x.L) < dist(x.R), но dist(x.R) <= logn. На каждом шаге, если нужно транспонируем и увеличиваем dist++, тогда dist увеличится до logn и обменов уже не надо будет делать.

[math]\triangleleft[/math]

Таким образом, мы восстановили левостороннесть кучи за O(logn) 3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. O(logn)

Построение кучи за О(n)

Храним список левосторонних куч. Пока их количество больше >1, из начала списка достаем две кучи, сливаем их и кладем в конец списка.

Преимущества левосторонней кучи

Нигде не делается уничтожающих присваиваний. Не создается новых узлов в merge. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация merge является персистентной.