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

Куча

Куча реализует очередь c приоритетами

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

Общее представление

Наша бинарная куча должна иметь эти функции:

• Add(key, value)
  

(Вставка(ключ, значение))

• Extract(key, value)
  

(Удаление(ключ, значение)
Всё работает за $ \Theta(\logn) $

двоичное дерево полное, означает, что заполнено слева направо и уровень не больше 1

---

Вставка

Посмотрим как можно добавить новый элемент:
В начале просто допишем наш элемент k как ребёнка к любому нашему родителю, у которого слева(справа) нет ребёнка
Но просто добавить его будет таким себе занятием, ибо может быть такое, что всё поломается, следовательно, нужно всё исправить
Ибо нам необходимо, чтобы для каждого нашей ноды работал HeapProperity:

Heap Properity

Для этого применим алгоритм SiftUp(i):

void SiftUp(Node* i)
{
  if(i != root)
    while(p[i]->key > i->key)
      swap(i)
  return;
}

При первом заходе в цикл меняется что-то только, если наше новое k меньше чем a,
Следовательно именно такой случай и рассмотрим:

Изменения после первого захода в цикл SiftUp

Здесь, всё что оказалось ниже, чем k будет верно, следовательно нужно проверять выше
Поэтому если d меньше, чем k, то снова заходим в цикл, иначе мы завершили

---

Извлечение

Извлечение у нас будет осуществляться алгоритмом SiftDown
Для этого нам необходимо поменять root с одним из leaf

После чего применить функцию SiftDown:

Условия для срабатывания SiftDown

Если родитель получается больше, чем дитё, тогда:

Если условия выполняются

$ \Theta(\log(height)) $ - SiftUp и SiftDown

---

Хранение

Как же хранить нашу кучу?
Ответ может удивить, ведь храним мы в обычном массиве(векторе)

Каждый leaf является 2*i + 1 или 2*i + 2 индексом parent

Соответственно в обычном представлении:
LeftChild(i) = 2*i + 1;
RightChild(i) = 2*i + 2;
Но некоторые умельцы начинают массив сразу с 1, чтобы использовалось меньше машинных операций(теперь индексы детей будут вычисляться как 2*i и 2*i + 1)

Heapify

$ \Theta(\log(n)) $
Heapify - преобразование массива к куче
А работает это за $ \Theta(\log(n)) $, так как:

for (i:[int/2...0])
    SiftDown(i);

n/2*1 + n/4 + n/8 * 3 + ...
$ n * \sum_n=1^{\infty} 1/{2^{n}} \smash 2 $