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

Материал из Викиконспекты
Перейти к: навигация, поиск
Левосторонняя куча

Содержание

[править] Условие кучи

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

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

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

Лемма (1):
В двоичном дереве с n вершинами существует свободная позиция на глубине не более \log{n}.
Доказательство:
\triangleright
Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более n.
\triangleleft

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


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


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

[править] Поддерживаемые операции

[править] merge

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

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

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

[править] insert

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

[править] extractMin

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

[править] delete

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

[править] decreaseKey

Лемма (2):
У левостороннего дерева с правой ветвью длины h количество узлов n \geqslant 2^{h} - 1.
Доказательство:
\triangleright

Индукция по h.

При h = 1 — верно.

При h > 1 левое и правое поддеревья исходного дерева левосторонние, а dist от их корней больше либо равен h - 1.

По индукции число узлов в каждом из них больше или равно 2^{h - 1} - 1, тогда во всем дереве n \geqslant (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.left) < dist(x.right), но dist(x.right) \leqslant \log{n}. На каждом шаге, если нужно транспонируем и увеличиваем dist, тогда dist увеличится до \log{n} и обменов уже не надо будет делать.
\triangleleft

Таким образом, мы восстановили левостороннесть кучи за O(\log{n}). Поэтому асимптотика операции \mathrm{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} \dfrac{n \cdot \log{n_i}}{2^i} =  n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{\log{2^i}}{2^i} =  n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \dfrac{i}{2^i}

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

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

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

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

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

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты