Биномиальные кучи

Биномиальное дерево

Биномиальное дерево $B_r$ ранга $r$ — дерево, определяемое рекурсивно: $B_0$ — дерево, состоящее просто из одного узла. $B_r$ состоит из двух биномиальных деревьев ранга $r-1$ , при корень одного из этих деревьев становится крайним левым ребёнком другого.

B_r = \cases{ \{\cdot\} & \if r = 0 \\ B_{r-1} \djunion \{ B_{r-1} \} & \if r \;\! \ge \;\! 1 }

Можно раскрыть рекурсию и получить эквивалентное определение. $B_r$ состоит из корня, у которого есть ровно $r$ детей — корни поддеревьев $B_0, B_1, \dotsc, B_{r-1}$ , расположенных в порядке убывания рангов.

B_r = \cases{ \{\cdot\} & \if r = 0 \\ \{ B_0 \} \djunion \{ B_1 \} \djunion \dotsb \djunion \{ B_{r-1} \} & \if r \;\! \ge \;\! 1 }

Отмечу сразу несколько очевидных свойств биномиальных деревьев.

В биномиальном дереве ранга $r$ содержится ровно $2^r$ вершин. Отсюда следует, что если в биномиальном дереве содержится $n$ вершин, то оно имеет ранг $\log_2 n$ .

Биномиальное дерево ранга $r$ имеет высоту $r+1$ , при этом на глубине $k$ содержится $\binom{r}{k}$ вершин. Корень такого дерева имеет степень $r$ , а все потомки имеют степень меньше $r$ . То есть если в биномиальном дереве содержится $n$ элементов, то максимальная степень произвольного узла равна $\log_2 n$ .

Биномиальная куча

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

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

Обязательно для каждого узла нужно хранить ранг поддерева с корнем в этом узле. Учтём, что ранг узла совпадает с его степенью.

Получается такая структура у узла

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

    int degree

    object priority

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

class heap:
    node* head
    node* max

Если heap.head оказывается равным none, то это значит, что куча пустая.

Поиск и получение максимума

Для получения максимума кучи достаточно просто пройти по ссылке на максимальный элемент

method get_max(heap h) -> node*:
    return h.max

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

method search_max(heap h) -> node*:
    node* candidate = none
    object max_priority = -infinity

    node* current = h.head

    while current is not none:
        if current.priority > max_priority:
            max_priority = current.priority
            candidate = current

        current = current.sibling

    return candidate

Так как корней биномиальных деревьев в лесу не более $\lfloor \log_2 n \rfloor + 1$ , операция поиска максимума выполнится за $O(\log n)$ .

Слияние двух биномиальных куч

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

Два биномиальных дерева одинакового ранга можно соединить в одно биномиальное дерево, ранг которого будет на $1$ больше. Если вдруг среди деревьев сливаемых куч окажется еще и дерево получившегося ранга, то их снова можно соединить.

Представим ранги деревьев в биномиальной куче как двоичное число: $j$ -й бит этого числа будет установлен в $1$ только если в биномиальной куче будет дерево ранга $j$ . Тогда процесс слияния двух биномиальных куч можно представить как сложение в двоичной системе двух чисел, представляющих собой ранги деревьев в обоих кучах.

classmethod merge(heap H1, heap H2) -> heap:
    if H1 is none:
        return H2
    if H2 is none:
        return H1

    heap H = {head = none}

    current_H = H.head
    current_H1 = H1.head
    current_H2 = H2.head

    # слияние корневых списков куч
    while current_H1 is not none and current_H2 is not none:
         if current_H1.degree < current_H2.degree:
             current_H.sibling = current_H1
             current_H = current_H1
             current_H1 = current_H1.sibling
        else:
             current_H.sibling = current_H2
             current_H = current_H2
             current_H2 = current_H2.sibling

    if current_H1 is none:
         while current_H2 is not none:
             current_H.sibling = current_H2
             current_H2 = current_H2.sibling

    else if current_H2 is none:
         while current_H1 is not none:
             current_H.sibling = current_H1
             current_H1 = current_H1.sibling

    # объединение деревьев одной степени
    current = H.head
    while current.sibling is not none:
         if current.degree == current.sibling.degree
             current.parent = current.sibling
             tmp = current.sibling
             current.sibling = current.sibling.child
             current = tmp
             continue
         current = current.sibling
    return H

Вставка

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