ТГиК-2019-Лекция-09.12.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Бинарная куча

рис.1. Пример кучи

Бинарная куча или пирамида (англ. Binary heap) — двоичное дерево, для которого выполнено следующее условие: значение в любой вершине не больше (если куча для минимума), чем значения её потомков (1)

Вся куча заполняется сверху вниз слева направо. Последний "слой" заполняется слева направо без пропусков (без "дырок")

Куча хранится в виде массива \(heap[0, ..., n-1]\). Нулевой элемент \(heap[0]\) — элемент в корне, наименьший элемент в куче (если куча создана по минимумам).

Как от родителей перейти к потомкам? Если элемент \(heap[i]\) - родитель, то левый потомок - \(heap[2i+1]\), правый потомок - \(heap[2i+2]\)

Как от потомка перейти к родителю? Если элемент \(heap[i]\) - потомок, то его родитель - \(heap[(i-1)/2]\)

Высота дерева

Пусть у нас есть дерево высоты \(h\). Какое минимальное количество вершин \(n1\) оно содержит?

Заметим, что в нулевом слое - одна вершина, в первом слое - две вершины, во втором слое - четыре вершины и так далее до h-го слоя. В слое с номером \(h-1\) будет \(2^{h-1}\) вершин, а в слое с номером \(h\) будет всего одна вершина, так как мы рассматриваем минимальное количество вершин для дерева высоты \(h\). Тогда минимальное количество вершин \(n1 = \sum^{h-1}_{i=0}{2^{i}} +1 = 1+ 2^0 + 2^{1} + 2^{2} + ... + 2^{h-1} = 2^{h} \).

Следовательно, \(h \le \log_2{n}\), где \(n\) - число вершин в дереве (общий случай)

Операции над бинарной кучей

siftUp

SiftUp - процедура, которая пересобирает кучу снизу вверх так, чтобы она удовлетворяла условию (1). В других источниках функция может называться Heapify_up

Если элемент больше своего отца, условие (1) соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем siftUp для этого отца. Иными словами, слишком маленький элемент всплывает наверх. Процедура выполняется за время \(O(log(n))\)

void siftUp (size_t i, vector<int>& heap){
   size_t par = (i-1)/2;

   while (i>0 && heap[i] < heap[par]){
      swap(heap[i],heap[par]);
      i = par;
      par = (i-1)/2;
 }
}

siftDown

SiftDown - процедура, которая пересобирает кучу сверху вниз так, чтобы она удовлетворяла условию (1). В других источниках функция может называться Heapify или Heapify_down

Если i-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами i-й элемент с наименьшим из его сыновей, после чего выполняем siftDown для этого сына. Процедура выполняется за время \(O(log(n))\)

void siftDown (size_t i, vector<int>& heap) {
   while (2*i+1 < heap.size()){
      size_t left = 2*i+1;
      size_t right = 2*i+2;
      size_t m = 2*i+1;
  
   if (right < heap.size() && heap[right] < heap[m]){
      m = right; 
   }
  
   if (heap[i] < heap[m]) break;
   swap(heap[i], heap[m]);
   i=m; 
  }
}

ExtractMin

ExtractMin - функция, которая извлекает минимальный элемент из кучи. Функция выполняется за время \(O(log(n))\). В других источниках функция может называться Min() или Heap_Extract_Min()

Извлечение выполняется в четыре этапа:

  1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
  2. Меняются местами корневой и последний элементы, последний элемент удаляется
  3. Вызывается siftDown для корня.
  4. Сохранённый элемент возвращается
int extractMin(vector<int>& heap){
   int min = heap[0];
   swap(heap[0],heap[heap.size()-1]);
   heap.erase(heap.begin() + heap.size()-1);
   siftDown(0,heap);
   return min; 
}

Создание кучи

Данная функция в других источниках может называться Build_Heap()

Дан массив \(heap[0, ..., n-1]\). Требуется построить кучу с минимумом в корне.

for (size_t i=heap.size()/2+1; i>0; --i){
  siftDown(i-1, heap);
}

Пирамидальная сортировка (Heapsort)

Для чего нужна бинарная куча? С её помощью можно отсортировать некоторый массив за \(O(n \log{n})\).

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

//создаём кучу
for (size_t i=heap.size()/2+1; i>0; --i){
  siftDown(i-1, heap);
}

vector<int> sortedArray;

while (!heap.empty()) {
  sortedArray.push_back(extractMin(heap));
}

return sortedArray;

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

рис.2. Жёлтые рёбра связывают кучи меньших порядков

Биномиальная куча (англ. binomial tree) — дерево, определяемое для каждого следующим образом

\(T_0\) — дерево, состоящее из одного узла;

\(T_k\) состоит из двух биномиальных деревьев \(T_{k-1}\), связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.

Свойство бинарной кучи также выполняется для биномиальной кучи. Примеры биномиальной кучи представлены на рис.2.

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

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

рис.3

Если у нас имеются две кучи одинаковой высоты (на рис.3а это кучи \(T_1\)), то для того, чтобы они стали одной кучей, нужно добавить новую связь так, чтобы сохранилось свойство бинарной кучи (рис.3б)

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

Пусть имеются две кучи \(h_1 \mbox{ и } h_2 \). \(h_1\) содержит \(T_1 , T_2 \), а \(h_2\) - \(T_1 , T_3\). Тогда слияние - это бинарное сложение с переносом. Это производится следующим образом:

1) Складываем кучи \(T_1\) в \(h_1 \mbox{ и } h_2 \). Получаем кучу \(T_2\)

2) Полученную кучу \(T_2\) можно сложить с кучей \(T_2\) из \(h_1\). Получаем кучу \(T_3\)

2) Полученную кучу \(T_3\) можно сложить с кучей \(T_3\) из \(h_2\). Получаем кучу \(T_4\)

рис.4. Слияние


Рассмотрим рис.4. В \(h_1\) кучи \(T_0, T_1\). В \(h_2\) кучи \(T_1, T_2\).

1) Добавляем в новую кучу элемент \(T_0\) из \(h_1\). Больше \(T_0\) нет

2) И в \(h_1\), и в \(h_2\) есть кучи порядка \(T_1\). Превращаем их в одну. Получаем кучу порядка \(T_2\)

3) В \(h_2\) есть куча порядка \(T_2\). Присоединяем её к полученной.

Слияние куч \(h_1 \mbox{ и } h_2 \) завершено.

Алгоритм слияния имеет сложность \(O(\log_2{n})\)

AVL - деревья поиска

рис.5

AVL-дерево - это сбалансированное по высоте двоичное дерево поиска. АVL — аббревиатура, образованная первыми буквами фамилий создателей (советских учёных) Георгия Максимовича Адельсон-Вельского и Евгения Михайловича Ландиса.

Сбалансированность означает то, что для каждой его вершины высота её двух поддеревьев различается не более чем на 1\[|h(L)-h(R)| \le 1\] Примеры сбалансированного и несбалансированного деревьев представлены на рис.5

рис.6. Схематичное изображение AVL-дерева

Главное свойство для всех поддеревьев (см.рис.6) - \(\forall x \in L \mbox{ } x \le r ; \forall x \in L \mbox{ } x \ge r \)

Высота AVL-дерева

Введём функцию \(N(h)\) - минимальное количество вершин в AVL-дереве высоты h. Например, \(N(0)=1, N(1)=2, N(2)=4\) и т.д.

Так как дерево сбалансированное, то \(h(L)=h(R)+1\). Очевидно, что так как дерево содержит минимальное количество вершин, то \(h(r)=h(L)=h(R)+1\). Переходя к функции \(N(h)\), получим \(N(h(r)) = 1+ N(h(L)) + N(h(R)) \Longrightarrow N(n+2) = 1+ N(n+1) + N(n)\)

Значит, \(N(n)>F_n \), где \(F_n \) - число Фибоначчи. Здесь мы выяснили, что асимптотика чисел Фибоначчи такова\[F_n \cong \frac{1}{\sqrt{5}}*{\left (\frac{1+\sqrt{5}}{2} \right )}^n \]. Отсюда можно сделать вывод о том, что асимптотика высоты AVL-дерева - \( log_w {n}, \mbox{ где } w=\frac{1+\sqrt{5}}{2}\)

рис.7. Правые повороты

Повороты

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

Заметим, что в базовой позиции у \(B\) была высота 2, а в 1 способе стала 1; у \(А\) была высота 0, а в 1 способе стала 1

Декартово дерево

Декартово дерево или Дерамида (англ Cartesian tree, Treap) - это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида). Более строго, это бинарное дерево, в узлах которого хранятся пары \((x,y)\), где \(x\) — это ключ, а \(y\) — это приоритет. Также оно является двоичным деревом поиска по \(x\) и пирамидой по \(y\).
Такая структура подходит для некоторого "Планировщика". Для Планировщика дерамида по времени - это пирамида. Планировщик умеет:

1) По времени добавить событие

2) Добавить событие с приоритетом

3) Удалить событие

4) Отсчитывать время