Скошенные и левосторонние кучи

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

Свободная позиция в двоичном дереве — место, куда может быть вставлен новый узел. То есть, если у какого-то узла нет какого-то ребёнка, то место этого несуществующего ребёнка является свободной позицией.

Теорема о минимальной свободной позиции

В бинарном дереве, содержащем $n$ вершин, существует свободная позиция на глубине не более $\lfloor \log_2 (n+1) \rfloor$ .

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

Для получения точной оценки достаточно рассмотреть полное бинарное дерево, в котором все свободные позиции находятся наиболее низко.

Давайте используем этот факт и сконструируем левостороннее дерево. Нам нужно потребовать выполнение следующего условия: ближайшая к корню свободная позиция должна быть самой правой позицией в дереве. Давайте формализуем и переформулируем в полее приятном виде.

Пусть $\dist v$ (free distance) — расстояние от узла $v$ до ближайшей свободной позиции в поддереве с корнем в $v$ . У пустых узлов $\dist (\code{\htmlClass{boolean}{none}}) = 0$ . Теперь наше требование можно переформулировать в более приятной форме:

\dist ( v.\code{left} ) \ge \dist (v.\code{right}) \quad\text{для всех узлов}~ v

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

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

Узлы такой левосторонней кучи должны хранить указатели на левого и правого ребёнка, а так же значение $\dist(v)$ , для того, чтобы не нужно было его пересчитывать каждый раз.

struct node:
    node* left
    node* right
    int dist
    int priority

При вычислении $\dist(v)$ для узла $v$ нужно отдельно проверить, не является ли этот узел none. Для удобства можно завести отдельную функцию, которую, кстати, надо инлайнить.

function get_dist(node x):
    if x is none:
        return 0
    else:
        return x.dist

Слияние левосторонних куч

Воспользуемся тем, что куча левосторонняя. Правое поддерево — самое короткое и не длиннее $\log n$ . Поэтому пойдём направо и сольем правое поддерево с кучей.

function merge(node* x, node* y):  # x и y являются корнями сливаемых куч
    if x is none:
        return y

    if y is none:
        return x

   if y.priority > x.priority:
       swap x, y

   x.right = merge(x.right, y)

   if get_dist(x.right) > get_dist(x.left):
       swap x.left, x.right

   x.dist = get_dist(x.right) + 1

   return x

Мы вызываем слияние рекурсивно, при этом каждый рекурсивный вызов у одной из сливаемых куч уменьшается высота. Значит, слияние будет работать за время $O(\log n)$ .

Более точно, слияние двух куч $H_1$ и $H_2$ с размерами $n_1$ и $n_2$ потребует $\dist H_1 + \dist H_2 = \lfloor \log_2 (n_1 + 1) \rfloor + \lfloor \log_2 (n_2 + 1) \rfloor$ рекурсивных вызовов.

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

Пусть дан массив $A$ размера $n$ с элементами, которые нужно собрать в кучу. Создадим из каждого элемента $A[i]$ отдельную левостороннюю кучу (один узел с $\dist = 1$ ), а затем будем объединять их в пары, пока не останется одна куча.

function build_leftist_heap(A: array[int]):
    n = A.length
    if n == 0:
        return none

    heaps = [new_node(A[i]) for i in 0 .. n-1] # Создаём массив куч по одной куче на элемент

    while heaps.length > 1:
        next_heaps = []
        for i in range(0, heaps.length, 2):
            left_heap = heaps[i]
            if i + 1 < heaps.length:
                right_heap = heaps[i + 1]
            else:
                right_heap = none
            merged = merge(left_heap, right_heap)
            next_heaps.append(merged)
        heaps = next_heaps

return heaps[0]

На каждом уровне итерации объединений количество куч уменьшается вдвое, а общее число операций merge — $n/2 + n/4 + n/8 + \dotsb = O(n)$ . Каждая операция merge в худшем случае занимает $O(\log n)$ , но так как размеры куч в начале малы, общая сложность построения — $O(n \log n)$ .

Вставка

Вставка нового элемента в кучу очень просто реализуется слиянием. Создаём новую левостороннюю кучу, состоящую только из одного элемента — вставляемого. Далее сливаем нашу новую кучу с исходной кучей, в которую вставляем элемент.

Извлечение минимума

Минимум находится в корне, поэтому для извлечения минимума достаточно просто удалить корень и слить его правое и левое поддеревья.

Скошенная куча

Скошенная куча (skew heap) — это разновидность левосторонней кучи, в которой отсутствует необходимость хранить и поддерживать значение $\dist(v)$ для каждого узла. Вместо этого скошенная куча на каждом шаге операции слияния она обязательно меняет местами левого и правого потомков у текущего узла. Это позволяет обойтись без хранения вспомогательных данных, при этом сохраняя амортизированную эффективность.

Узел скошенной кучи содержит только указатели на левого и правого потомков и значение приоритета.

struct node:
    node* left
    node* right
    int priority

Операция merge — основная для скошенной кучи. В отличие от левосторонней кучи, где на каждом шаге проверяется и поддерживается свойство $\dist$ , в скошенной куче мы просто меняем местами левого и правого потомков после рекурсивного слияния.

function merge(node* x, node* y):
    if x is none:
        return y

    if y is none:
        return x

    if y.priority < x.priority:
        swap x, y

    x.left = merge(x.left, y)
    swap x.left, x.right

    return x

Помимо merge, все операции реализуются идентично левосторонней куче, то есть построение/вставка/удаление отличаются, только приниципом работы функции merge.

Как мы поняли в отличие от левосторонней кучи, в скошенной куче не проверяется соотношение между левым и правым поддеревом. Вместо этого, после рекурсивного вызова merge(x.left, y), мы всегда меняем местами левого и правого потомков у x. Из этого следует явное замечание о том, что в худшем случаем merge имеет сложность $O(n)$ операций, но вся ассимптотическая прелесть скошенной кучи раскрывается при большом количестве операций merge, что бы удостовериться в этом проведем амортизационный анализ.

Амортизационный анализ скошенной кучи

Для того что бы найти примерную сложность операции merge воспользуемся потенциальным методом анализа.

Потенциал скошенной кучи

Пусть $H$ — скошенная куча. Определим её потенциал $\Phi(H)$ как количество правых детей в дереве, то есть число узлов, которые являются правыми потомками своих родителей.

Интуитивно заметно, что потенциал измеряет «несбалансированность» кучи, то есть чем больше правых потомков, тем выше потенциал. При каждом вызове merge мы меняем местами левого и правого потомков у корня, что может уменьшить потенциал, компенсируя стоимость будущих операций.

Амортизированная сложность слияния

Амортизированная стоимость операции merge для двух скошенных куч с суммарным размером $n$ составляет $O(\log n)$ .

Пусть операция merge выполняет $t$ рекурсивных вызовов. В худшем случае $t = O(n)$ , но рассмотрим амортизированную стоимость $\hat{c} = t + \Delta\Phi$ , где $t$ — реальная стоимость (число рекурсивных вызовов), а $\Delta\Phi = \Phi_{\text{после}} - \Phi_{\text{до}}$ — изменение потенциала.

То есть, при каждом рекурсивном вызове мы поднимаем одно из сливаемых деревьев по правому пути, но после операции merge все узлы на этом пути становятся левыми потомками, что уменьшает потенциал. Выражаясь формально $\Delta\Phi \le -t + 2 \log n$ .

Подставим в формулу амортизирвоанной сложности и получим:

\hat{c} = t + \Delta\Phi \le t + (-t + 2 \log n) = 2 \log n = O(\log n).

Таким образом, хотя отдельные вызовы могут быть дорогими, путем постоянного хаотичного пермешивания кучи мы смогли добиться сложности $O(\log n)$ , при этом сохранив память не сохраняя $\dist(v)$ в каждом узле.

Отсюда следует нехитрый вывод: если нам критически важно поведение структуры данных в worst-case ситуации, то стоит прибегать к реализации левосторонней кучи, а если количество операций с кучей большое и нам важно сохранить память, то скошенная куча будет эффективнее.

Задачи

1. Почему в скошенной куче нельзя заменить swap x.left, x.right на swap x.right, x.left в коде слияния? Что изменится?

2. Пусть в левосторонней куче узел $v$ имеет $\dist(v) = k$ . Какое минимальное количество узлов должно быть в поддереве с корнем $v$ ?

3. Реализуйте скошенную кучу и функции для нее.

4. Реализуйте правостороннюю кучу и функции для нее.