Фибоначчиева куча

Давайте вспомним, как работает биномиальная куча. Биномиальная куча представляет собой лес из куч. Слияние двух биномиальных куч реализовывалось соединением списков корней деревьев в обоих лесах. Потом мы, конечно, восстанавливали свойства биномиальной кучи после слияния, что как раз и давало нам временную сложность $O(\log n)$ . Но сама идея реализации слияния двух куч через обычное соединение списков корней не такая уж и плохая.

Давайте уберем жёсткую структуру леса и каждого дерева в лесе. У нас получилась основа для фибоначчиевой кучи, которую можно доделать и превратить в приоритетную очередь с очень хорошими оценками времени работы.

Фибоначчиева куча

Фибоначчиева куча — набор деревьев, каждое из которых удовлетворяет свойству кучи: приоритет каждого узла не меньше приоритетов его детей.

Степенью фибоначчиевой кучи $H$ будем называть максимальную степень узла в этой куче:

\deg H \defeq \max\limits \{ \deg v \mid \forall\, v \in H \} = D

Хранить фибоначчиеву кучу будем почти так же, как биномиальную. Единственное, из-за свободной структуры, нам не будет хватать односвязного списка для хранения детей узла. Чтобы была возможность удалять узлы из произвольного места и вставлять узлы в произвольное место, будем хранить детей в циклическом двузвязном списке.

Ещё нам понадобится хранить бинарную метку для каждой вершины. Это нужно для эффективной реализации операций удаления узла и изменения приоритета узла.

struct node:
    node* parent  # ссылка на родителя
    node* left    # ссылка на левого брата
    node* right   # ссылка на правого брата
    node* child   # ссылка на какого-то ребёнка

    int degree
    bool mark

    object priority

Для доступа ко всем деревьям леса нам достаточно всего одного указателя, ведь корни тоже хранятся в двусвязном списке. Разумно хранить именно указатель на элемент с максимальным приоритетом. Такой элемент всегда является корнем одного из деревьев в лесу.

Также будем хранить размер кучи для обеспечения константного времени получения этого размера

class heap:
    int size
    node* max

Нам очень часто нужно будет объединять списки узлов, поэтому стоит оформить эту операцию как отдельную функцию

function union_lists(node* first, node* second):
    node* left = first.left
    node* right = second.right

    second.right = first
    first.left = second

    left.right = right
    right.left = left

При анализе времени работы операций будем использовать метод потенциалов. Пусть потенциал кучи $H$ будет равен

\Phi(H) \defeq t(H) + 2 \cdot m(H)

где $t(H)$ — количество деревьев в корневом списке кучи $H$ , и $m(H)$ — количество отмеченных вершин в куче $H$ , то есть узлов, у которых поле marked установлено в true.

Создание пустой кучи

Для создания пустой кучи достаточно просто создать объект класса heap, у которого $\code{size} = 0$ и $\code{max} = \code{\htmlClass{boolean}{null}}$ .

initialize(self):
    self.size = 0
    self.max = null

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

Сама операция создания пустой кучи выполняется за $O(1)$ .

Слияние

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

method merge(heap self, heap other):
   if other.size == 0:
       return

   if self.size == 0:
       self.max = other.max
       self.size = other.size
       return

   union_lists(self.max, other.max)
   self.size += other.size

   if other.max > self.max:
       self.max = other.max

Потенциал не меняется, поскольку до слияния куч $H_1$ и $H_2$ общий потенциал был равен $\Phi(H_1) + \Phi(H_2)$ , а после слияния потенциал у полученной кучи равен $\Phi(H_1 \union H_2) = \Phi(H_1) + \Phi(H_2)$ . Общее число узлов в корневых списках и общее число помеченных вершин остаётся тем же.

Временная сложность работы операции слияния $O(1)$ .

Вставка

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

Можно оптимизировать эту операцию, избавившись от парочки ветвлений и присвоений указателей. Нам надо просто создать новый узел и добавить его в список корней, пересчитав максимум.

method insert(heap self, object priority):
    node new_node = {
        priority = priority,
        degree = 0,
        child = null,
        mark = false,
    }

    if size == 0:
         self.max = new_node
         self.max.left = new_node
         self.max.right = new_node
    else:
         node previous_right = self.max.right
         self.max.right = new_node
         new_node.left = self.max
         new_node.right = previous_right
         previous_right.left = node_node

    if node_node.priority > self.max.priority:
         self.max = node_node

    self.size++

В отличие от вставки в биномиальную кучу, здесь мы не выполняем никаких операций объединения деревьев. То есть если мы подряд вставим $k$ новых узлов в фибоначчиеву кучу, то список корней увеличится на $k$ элементов.

После этой операции в корневой список добавилась один узел, значит потенциал увеличился на $1$ . Время работы операции вставки составляет $O(1)$ .

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

Максимум в куче находится по ссылке max. Можно разрушить дерево с корнем max, удалить узел max, а получившийся список детей рассмотреть как новую кучу. Тогда просто слить эту кучу из детей с исходной кучей без дерева с корнем в max.

Проблема в том, что после удаления старого максимума нам нужно найти новый максимум. Также именно на этом этапе нам нужно перестроить кучу, чтобы деревьев в ней было не слишком много, и будущие операции занимали небольшое количество времени. Обе эти задачи может решить операция consolidate (уплотнение), которую я буду именовать окучиванием. Окучивание разберем чуть позже, а пока код самого извлечения:

method extract_max(heap self) -> node:
    node z = self.max
    if z is null: return null

    if z.child is not null:
        node child = z.child
        node start_child = child

        do:
            node next_child = child.right

            # Добавляем child в корневой список
            child.parent = null
            child.left = self.max
            child.right = self.max.right
            self.max.right.left = child
            self.max.right = child

            child = next_child

        while child != start_child

    # Удаляем z из корневого списка
    z.left.right = z.right
    z.right.left = z.left

    # Обновляем self.max
    if z.right == z:  # В корневом списке был только z
        self.max = null
    else:
        self.max = z.right
        self.consolidate()

    self.size--
    return z

Окучивание

Вспомогательная операция окучивания принимает на вход фибоначчиеву кучу $H$ и преобразует её таким образом, что в списке корней деревьев результирующей кучи будет содержаться не более $D + 1$ узлов.

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

Заведём таблицу $\code{p} \bigl[ 0 \dots D \bigr]$ , в которой будем хранить ссылки на корни. Точнее, $\code{p}[j]$ будет содержать в себе ссылку на корень дерева, степень которого равна $j$ .

Теперь мы можем организовать процесс, аналогичный процессу слияния биномиальных куч. Проходимся поочередно по всем корням деревьев в кусе, смотря на его степень. Пусть степень текущего корня равна $d$ . Если в ячейке $\code{p}[d]$ нет ссылки, то записываем туда ссылку на текущий корень. Если там что-то есть, то соединяем то дерево, на которое ссылается $\code{p}[d]$ и текущее дерево, и включим получившееся дерево в наш проход следующим.

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

method consolidate(heap self):
    table[node*] p[]

    node* current = self.max
    node* start = self.max

    do:
        node* next = current.right
        degree = current.degree

        while p[degree] is not null:
            node* conflict = p[degree]
            if conflict.priority > current.priority:
                swap current, conflict

            # удалить узел conflict из списка корней
            conflict.left.right = conflict.right
            conflict.right.left = conflict.left
            conflict.parent = null

            # добавить к current ребёнка conflict
            conflict.parent = current
            conflict.left = conflict
            conflict.right = conflict
            if current.child == null:
                current.child = conflict
            else:
                union_lists(current.child, conflict)
            current.degree++

            p[degree] = null
            degree += 1

        p[degree] = current
        if current.priority > self.max.priority:
            self.max = current

        current = next

    while current != start

Посмотрим, сколько времени занимает операция извлечения максимума. Пусть до извлечения максимума в куче было $t$ деревьев и $m$ помеченных узлов. И пусть у максимального элемента в куче степень равна $d$ .

До разрушения дерева с максимальным корнем потенциал кучи был равен $t + 2m$ . После разрушения и добавления детей потенциал стал равен $(t-1+d) + 2m$ . Получается, что разность потенциалов равна $\Delta \Phi_1 = \bigl( (t-1+d) + 2m \bigr) - (t + 2m) = d-1$ , а реальная стоимость чистого извлечения равна $c_1 = d+1$ .

После этого шага в списке корней у нас находится $t' = t-1+d$ узлов. После окучивания останется не более $D+1$ деревьев. Тогда разность потенциалов $\Delta \Phi_2 \le (D + 1 + 2m) - (t' + 2m) = D+1-t'$ , а реальная стоимость окучивания $c_2 = t' + D$ .

Получается, что суммарное изменение потенциала

\Delta \Phi = \Delta \Phi_1 + \Delta \Phi_2 \le (d-1) + (D+1-t') = d + D - (t-1+d) = D-t+1

Получаем, что амортизированная сложность извлечения максимума вместе с окучванием

A = c_1 + c_2 + \Delta \Phi \le (d + 1) + (t' + D) + (D - t + 1) = 2d + 2D + 1

Поскольку $D = \deg H$ — максимальная степень узла, то $d \le D$ . Получаем верхнюю оценку

A \le 4D + 1

Изменение приоритетов

Увеличение приоритета

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

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

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

Будем следить, чтобы у каждой вершины, не входящих в корневой список, удалялось не более одного ребёнка. Для этого мы и заводили бинарную метку mark. Если у узла $x$ удаляли ребёнка, то $x.\code{mark} = \true$ . По этому после вырезания ребёнка у узла этот узел помечается, если он ранее не был отмечен и если он не является корнем. Если же он был отмечен, то он тоже вырезается, и процедура уходит дальше по родителям. Описанная процедура последовательного вырезания отмеченных вершин называется каскадным вырезанием.

method promote(heap self, node* x, object new_priority):
   if new_priority > x.parent.key:
       x.priority = new_priority
       return

   node parent = x.parent
   self.cut(x)
   self.cascading_cut(parent)

Вырезание узла.

Когда мы вырезаем узел, мы убираем его из списка детей его родителя, уменьшаем степень родителя на $1$ и вставляем его в корневой список. Обязательно нужно снять метку, так как узел стал корнём.

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

method cut(heap self, node* x)
   node left = x.left
   node right = x.right
   right.left = left
   left.right = right
   x.parent.degree--

   if x.parent.child == x:
       if x.right == x:
           x.parent.child
       else:
           x.parent.child = x.right

   x.right = x
   x.left = x
   x.parent = null
   x.mark = false

   union_lists(self.min, x)  # вставляем наше поддерево в корневой список

Каскадное вырезание.

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

method cascading_cut(heap self, node* x)
   while x.mark == true:
       self.cut(x)
       x = x.parent
   x.mark = true

Посмотрим, сколько времени занимает операция увеличения приоритета. Внутри себя эта операция вызывает еще вспомогательные операции вырезания и каскадного вырезания.

Реальная стоимость всех этих операций описывается длиной цепочки рекурсивных вызовов. Обозначим эту длину за $c$ . А сама цепочка рекурсивных вызовов соответствует цепочке помеченных узлов, каждый из которых является ребёнком следующего. Все вершины из этой цепочки помещаются в корень и остаются непомеченными, так что реальная стоимость всей операции увеличения приоритета равна $c$ .

Анализ алгоритмов

Давайте теперь оценим размеры поддеревьев.

Лемма о размере поддеревьев в фибоначчиевой куче

Пусть $x$ — какой-то узел в фибоначчиевой куче, $\deg x$ — количество детей этого узла $x$ , и $\size x$ — минимально возможный размер поддерева с корнем в $x$ .

Минимальный возможный размер поддерева с корнем степени $k$ не меньше $F_{k+2}$ , то есть

\deg x = k \implies \size x \ge F_{k+2}

Доказать эту лемму можно индукцией по $k$ . База $k=0$ : дерево состоит только из корня, $\size(x) = 1 = F_2$ , и $k=1$ : дерево состоит из корня и одного его ребёнка, $\size(x) = 2 = F_3$ .

Пусть у узла $x$ детьми являются узлы $y_1, y_2, \dotsc, y_k$ , при этом дети упорядочены по времени добавления. Когда узел $y_j$ стал ребёнком узла $x$ , у узла $x$ уже было $j-1$ детей, поэтому в момент добавления $\deg y_j = j - 1$ , поскольку соединяются деревья с одинаковой степенью корня.

Далее у узла $y_j$ могли вырезать ребёнка, если выполнялась операция увеличения приоритета. Но у узла $y_j$ могли вырезать максимум одного ребёнка, ведь после вырезания первого ребёнка узел $y_j$ стал помеченным, то есть $y_j.\code{mark} = \code{\htmlClass{boolean}{true}}$ , а при удалении второго ребёнка сработало бы каскадное вырезание, и узел $y_j$ перестал бы быть ребёнком узла $x$ . Значит, за всё время у узла $y_j$ могли удалить только одного ребёнка из тех, что были в момент добавления, то есть

\deg y_j \ge j-2 \quad\text{для всех}~ 1 \le j \le k ~\text{в любой момент после добавления}

Получается, что по предположению индукции,

\size(y_j) \ge F_{\deg y_j + 2} \;\! \ge \;\! F_{(j-2)+2} = F_j

Тогда

\size x \ge 1 + \sum\limits_{j=1}^k \size y_j \;\! \ge \;\! 1 + \sum\limits_{j=1}^k F_j = F_{k+2}

Используем результат леммы, чтобы оценить $D$ , максимальная степень узла.

Суммарное количество узлов в куче не меньше размера поддерева с корнем в узле, имеющем максимальную степень. То есть, если в куче $n$ элементов, то

n \ge \size (\text{узел степени}~ D) \ge F_{D+2}

Отсюда можно получить оценку для $D$ , логарифмируя неравенство $n \ge F_{D+2}$

\log_\varphi n \ge \log_\varphi F_{D+2} = D + 2 - \log_\varphi \sqrt{5} + O(\varphi^{-2D}) \implies D \;\! \le \;\! \log_\varphi n + \log_\varphi \sqrt{5} - 2 + o(1)

Запишем отдельно наш результат, из которого следуют временные оценки сложности операций извлечения минимума и увеличения приоритета

D \le \log_\varphi n + \log_\varphi \sqrt{5} - 2 + o(1) \quad\text{и}\quad D \le \lfloor \log_\varphi n \rfloor + 1