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

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

Определение

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

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

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

Свободной позицией назовем место в дереве, куда может быть вставлена новая вершина. Само дерево будет являться свободной позицией, если оно не содержит вершин. Если же у какой-то внутренней вершины нет сына, то на его месте — свободная позиция.

Лемма (1):

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

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

$\triangleright$

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

$\triangleleft$

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

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

Условие левосторонней кучи. Пусть $dist(u)$ — расстояние от вершины $u$ до ближайшей свободной позиции в ее поддереве. У пустых позиций $dist = 0$. Тогда потребуем для любой вершины $u : dist(u.L)\ge dict(u.R)$.

Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за $O(1)$ поменять местами левого и правого ребенка, что не повлияет на порядок кучи.

Поддерживаемые операции

merge

Слияние двух куч.

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

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

insert

Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.

extractMin

Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.

delete

Аналогично удаляется любой элемент — на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя — на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью $decrease key$. Уменьшаем ключ до $-\infty$, затем извлекаем минимальное значение.

decreaseKey

Лемма (2):

У левостороннего дерева с правой ветвью длинны $h$ количество узлов $n \ge 2^{h} - 1$.

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

$\triangleright$

Индукция по h. При $h = 1$ — верно. При $h \gt 1$ левое и правое поддеревья исходного дерева левосторонние, а $dist$ от их корней больше либо равен $h - 1$. По индукции число узлов в каждом из них больше или равно $2^{h - 1} - 1$, тогда во все дереве $n \ge (2^{h - 1} - 1) + (2^{h - 1} - 1) + 1 = 2^{h} - 1$ узлов.

$\triangleleft$

Алгоритм

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

Лемма (3):

Нужно транспонировать не более $\log{n}$ поддеревьев.

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

$\triangleright$

Длина пути от вершины до корня может быть и $O(n)$, но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левосторонней кучи уже выполнено. Транспонируем только если $dist(x.L) \lt dist(x.R)$, но $dist(x.R) \le \log{n}$. На каждом шаге, если нужно транспонируем и увеличиваем $dist++$, тогда $dist$ увеличится до $\log{n}$ и обменов уже не надо будет делать.

$\triangleleft$

Таким образом, мы восстановили левостороннесть кучи за $O(\log{n})$. Поэтому асимптотика операции $decreaseKey$ — $O(\log{n})$.

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

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

Покажем, почему это будет работать за $O(n)$.

Пусть на $i$-ом шаге алгоритма в нашем списке остались только кучи размера $2^i$. На нулевом шаге у нас $n$ куч из одного элемента, и на каждом следующем количество куч будет уменьшаться вдвое, а число вершин в куче будет увеличиваться вдвое. Слияние двух куч из $n_i$ элементов выполняется за $O(\log{n_i})$. Поэтому построение будет выполняться за

$\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{n \cdot \log{n_i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{\log{2^i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i}$

Покажем, что сумма — $O(1)$, тогда и алгоритм будет выполняться за $O(n)$. Найдём сумму ряда, заменив его на эквивалентный функциональный:

$\sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}{i}{2^i} \lt \sum\limits_{i = 1}^{\infty } \genfrac{}{}{}{0}{i}{2^i} \\ f(x) = \sum\limits_{i = 1}^{\infty } \Bigl. i \cdot x^i \Bigr|_{x = \frac{1}{2}}, ~\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } i \cdot x^{i - 1}, ~\int\genfrac{}{}{}{0}{f(x)}{x} = \sum\limits_{i = 1}^{\infty } x^i =~\genfrac{}{}{}{0}{1}{1 - x} - 1, \\ ~\genfrac{}{}{}{0}{f(x)}{x} = (\genfrac{}{}{}{0}{1}{1 - x} - 1)' = \genfrac{}{}{}{0}{1}{(1 - x)^2}, ~f(x) = \genfrac{}{}{}{0}{x}{(1 - x)^2}$

После подстановки $x = \genfrac{}{}{}{0}{1}{2}$ получаем, что сумма равна $2$. Следовательно, построение кучи таким образом произойдёт за $O(n)$.

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

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

Ссылки

1. Лекция "Приоритетные очереди" А. С. Станкевича в Computer Science Center

2. Левосторонние кучи. Интуит.

3. Wikipedia — Leftist tree