пятница, 27 мая 2011 г.

Биномиальная куча(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: В ходе реализации возникла потребность создавать глубокую копию биномиальных куч, поэтому были дописаны конструкторы копирования для биномиальных куч и узлов пирамидальных деревьев.

четверг, 26 мая 2011 г.

Приоритетная очередь(priority_queue)

                          [по мотивам приоритетной очереди Robert Sedgewick]

Данный пост находится в стадии разработки.

Промежуточные материалы пока лежат здесь:

priority_queue.h
main.cpp

среда, 25 мая 2011 г.

Занятие №3. Алгоритмы поиска в олимпиадных задачах

Теория: Лекция                                             [Все занятия]

Лекция шикарная. Особо понравилось описание “бинарного поиска по ответу”. Также произвел впечатление описанный подход с выявлением радиоактивного шарика и нахождения фальшивой монеты.

Практика:                                         [Официальная страница]
Учебные задачи: 
  
Задача A. 
   [Номер максимального элемента]
   Классика жанра. Даже не знаю, что еще можно добавить.
 
   Задача B. 
   [Сложность двоичного поиска]
   Суть задачи сводится к нахождению значения log(n) по основанию 2, округленного в большую сторону.
   Задача С. 
  
[Двоичный поиск]
   Классическая задача на проверку корректной реализации на бинарный поиск. Базовую реализацию и частные случаи бинарного поиска мы уже рассматривали ранее в этом посте. 
Олимпиадные задачи: 
   Задача A. 
  
[Забавный конфуз]
   Задача на умение работать с одномерным массивом. 
   Задача B. 
   [Черепаха]
   Решение полностью соответствует авторскому разбору. Главное в задаче выделить монотонную функцию, применив затем к ней бинарный поиск для нахождения корней. Хороший пример, иллюстрирующий подход бинарного поиска по ответу.

   Задача С.
  
[Очень легкая задача]
   Казалось бы задача, как задача. И даже разбор полный дан в лекции и сама по себе задача несложная. Но есть в ней один интересный момент. Перед дихотомией нужно чем то инициализировать верхнюю границу подбираемого значения. В первом своем решение я взял n*max(x,y), т.е. печатаем все страницы на самом медленном принтере. С типами все в порядке. B вдруг получаем TLE на последнем тесте. В исходнике двухлетней давности я взял в качестве этого параметра n*min(x,y). Казалось бы какая разница? Но старое решение заходит, а новое нет. Отмечу, что вычисления идут в интах.
Рассмотрим граничный тест: 2e8 10 9.
Инициализация:   l = 0;       r = 1.8e9
Первая итерация: l = 0.9e9+1; r = 1.8e9
Вторая итерация: l + r = 2.7e9 – Переполнение типа.
В итоге середина сойдется к числу меньшему 1e9. В старом решении не происходило переполнения типа только потому что после первой итерации дихотомии правая граница становилась 1e9 и в дальнейшем переполнение исключалось.
Такие случаи конечно нужно просчитывать предварительно, но чтобы спать спокойно сейчас я решил ее в long long’ах =)
Дополнительные олимпиадные задачи:
   Задача A. 
   [Медиана объединения] merge 
  
С ходу можно предложить слияние двух массив в один отсортированный. Сложность merge O(N)
   [Медиана объединения] kth_element
   Также данную задачу можно решить с помощью нахождения k-ой порядковой статистики. Данный алгоритм имеет ту же линейную сложность, что и первое решение, но константа будет больше, т.к. имеют место копирование двух подмассивов в один.
   Задача B. 
   [Столица]
   Умение находить k-ую порядковую статистику в этой задаче может ускорить решение, но ограничения позволяют сделать полную сортировку. 
   Задача С.
   [Выборы]
 
Шикарная задача. Суть задачи сводится к нахождению стоимости политической партии. Для каждой партии бинарным поиском подбираем количество голосов, которые необходимо набрать этой партии для победы. Далее с помощью функции lower_bound проверяем корректность выбранного количества голосов. В итоге имеем 2 сортировки, 2 бинсерча + очевидное ДП.