Биномиальная куча(binomial queue)

Литература: Алгоритмы на С++. Роберт Седжвик

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

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

Введем понятие Пирамидального дерева. Это двоичное дерево размером 2^N, в котором для каждого узла выполняется правило:
Все элементы левого поддерева не превышают значение текущего элемента.

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

Рассмотрим пример:
Известно, что биномиальная куча содержит 11 элементов. Это означает, что она состоит из 3 пирамидальных деревьев с размерами: 8, 2 и 1. Чтобы повторить эту операцию для произвольного размера биномиальной кучи необходимо представить этот размер в двоичном виде и взять степени двойки, соответствующие единичным битам в разложении. 11(10) = 1011(2) = 8 + 2 + 1.

Вот примеры правильных пирамидальных деревьев размером 1, 2, 4, 8:

Узел пирамидального дерева и сама биномиальная куча в коде будут представлены следующими структурами:

1. const int SIZE = 31;
2. struct Node {
3.   int data;
4.   Node* left;
5.   Node* right;
6. };
7.  
8. struct binomial_queue {
9.   Node* mas[SIZE];
10.   int size;
11. };

* This source code was highlighted with Source Code Highlighter.

Сразу виден главный минус реализации биномиальной кучи. Это дополнительные 8 байтов, которые нужно тратиться для каждого элемента, чтобы иметь связь с правым и левым поддеревом.

Рассмотрим более подробно 5 операций:

1) Объединение двух пирамидальных деревьев в одну.
2) Добавление элемента в биномиальную кучу
3) Поиск максимального элемента в биномиальной куче
4) Объединение двух биномиальных куч произвольного размера
5) Удаление максимального элемента из биномиальной кучи

1) Объединение двух пирамидальных деревьев в одну.
Сразу отметим тот факт, что объединять можно только пирамидальные деревья одинакового размера, т.к. только такое правило позволит получать в результате дерево размерностью 2^n. Рассмотрим два дерева размерностью 4:

В результате объединения получится дерево размерностью 8:

Объединение происходит по следующим правилам:
1) В корне результирующего дерева находится максимальный из корней исходных деревьев
2) Левое поддерево максимального корня становится правым поддеревом меньшего корня.

Как можно заметить для выполнения этой операции нужно просто грамотно переопределить ссылки:

1. Node* join(Node* f, Node *s) {
2.   if (f->data > s->data) {
3.     s->right = f->left; f->left = s; return f;
4.   }
5.   else {
6.     f->right = s->left; s->left = f; return s;
7.   }
8. }

* This source code was highlighted with Source Code Highlighter.

В качестве параметров передаются указатель на корни двух объединяющихся деревьев. Результатом работы функции является указатель на корень объединенных деревьев.

2) Добавление элемента в биномиальную кучу
Эта операция полностью повторяет логику сложения двух двоичных чисел. Допустим нам нужно сложить 11 и 1.

                                          1011 
                                       +  0001 
                                       ------- 
                                          1100

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

1. void add(int val) {
2.   Node* newNode = new Node(val);
3.   Node* curNode = newNode;
4.   for (int i=0;i<SIZE;i++) {
5.     if (mas[i] == NULL) {
6.       mas[i] = curNode;
7.       break;
8.     }
9.     else {
10.       curNode = join(curNode,mas[i]);
11.       mas[i] = NULL;
12.     }
13.   }
14.   size++;
15. }

* This source code was highlighted with Source Code Highlighter.

3) Поиск максимального элемента в биномиальной куче
Корень каждого пирамидального дерева является максимальным элементов в данном дереве. Поэтому для поиска максимального элемента в биномиальной куче нужно последовательно перебрать все корни пирамидальных деревьев и выбрать максимальный.
4) Объединение двух биномиальных куч произвольного размера
Эта операция полностью повторяет процесс сложения двух двоичных чисел. При этом операнды и перенос при сложении принимают значения 0 или 1. Т.е. возникает 8 различных ситуаций. Касательно биномиальных куч эта операция может выглядеть вот так:

1. void joinBQ(Node* a[], Node* b[SIZE]) {
2.     Node* c = 0;
3.     for (int i=0;i<SIZE;i++) {
4.       switch(num(c!=0,b[i]!=0,a[i]!=0)) {
5.         case 2: a[i] = b[i]; break;
6.         case 3: c = join(a[i],b[i]); a[i] = 0; break;
7.         case 4: a[i] = c; c = 0; break;
8.         case 5: c = join(a[i],c); a[i] = 0; break;
9.         case 6:
10.         case 7: c = join(b[i],c); break;
11.       }
12.     }
13. }
14. void joinBQ(binomial_queue &bq) {
15.     joinBQ(mas, bq.mas);
16.     size += bq.size;
17. }

* This source code was highlighted with Source Code Highlighter.

5) Удаление максимального элемента из биномиальной кучи
Прежде чем удалить максимальный элемент из биномиальной кучи нужно найти его пирамидальное дерево, в котором он содержится, воспользовавшись п.2):

Исходное дерево содержит 8 узлов. После удаления корня пирамидального дерева останется три пирамидальных дерева размерностью 4,2 и 1: 
Эти деревья можно поместить во временную биномиальную кучу. После чего объединить её с текущей.
Все вышесказанное можно реализовать с помощью следующего кода:

1. int getMax() {
2.   int res = 0;
3.   int resPos = -1;
4.   for (int i=0;i<SIZE;i++) {
5.     if (mas[i] && mas[i]->data > res) {
6.       res = mas[i]->data;
7.       resPos = i;
8.     }
9.   }
10.   Node** tmp = new Node*[SIZE];
11.   memset(tmp,0,sizeof(tmp)*SIZE);
12.   Node* cur = mas[resPos]->left;
13.   for (int i=resPos-1;i>=0;i--) {
14.     tmp[i] = new Node(*cur);
15.     cur = cur->right;
16.     tmp[i]->right = 0;
17.   }
18.   delete mas[resPos];
19.   mas[resPos] = 0;
20.  
21.   joinBQ(mas, tmp);
22.   delete tmp;
23.   size--;
24.   return res;
25. }

* This source code was highlighted with Source Code Highlighter.

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