Куча(Очередь с приоритетами)

Материал из Algocode wiki
Версия от 17:42, 18 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «==Куча== Подвешенное дерево - дерево, у которого есть корень. Двоичная Куча - такое подвеш...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Куча

Подвешенное дерево - дерево, у которого есть корень.

Двоичная Куча - такое подвешенное дерево, для которого выполнены три условия:

1) Значение в любой вершине не меньше, чем значения её потомков.

2) У любой вершины не более двух сыновей.

3) Слои заполняются последовательно слева направо сверху вниз.

Правильная куча(https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/240px-Max-Heap.svg.png)

Давайте обозначим как $h$ высоту кучи.

Куча также умеет 3 основные операции :

1) найти минимум за $O(1)$

2) удалить минимум за $O(h)$

3) добавление нового ключа в кучу за $O(h)$

Так как куча всегда состоит из нескольких слоев заполненых полностью и одного частично и каждый слой содержит в два раза больше вершин, чем предыдущий, то можно понять, что высота дерева будет не больше $O(log(N))$.

еперь давайте поговорим о том, как же реализовать такую структуру.

Хранить кучу мы будем в виде массива, где у корня индекс равен $1$, и у вершины $n$ индексы ее потомков - $2n$ и $2n + 1$. Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией Up.

Запускаемся из элемента $i$. Если элемент больше своего отца, то больше ничего делать не нужно. Иначе, мы меняем местами его с отцом и запускаемся от отца. В результате такой функции мы исправим случаи, когда первое условие кучи не соблюдается. Так как каждый раз мы только поднимаемся, то работать функция будет за количество предков вершины, а оно максимум равно высоте дерева.

void Up(int i) {
    while (i > 1 && a[i] < a[i / 2]) {    // i = 1 — корень
        swap(a[i], a[i / 2]);
        i = i / 2;
    }
}

Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией Down. Запускаемя от элемента $i$, если $i$-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами $i$-й элемент с наименьшим из его сыновей, после чего выполняем Down для этого сына. Так как каждый раз мы спускаемся только в одного сына, то работать функция будет за высоту дерева.

void Down(int i) {
    while (2 * i < size) {    // size — количество элементов в куче
        left = 2 * i;             // left — левый сын
        right = 2 * i + 1;            // right — правый сын
        j = left;
        if (right < size && a[right] < a[left]) {
            j = right;
        }
        if (a[i] <= a[j]) {
            break;
        }
        swap(a[i], a[j]);
        i = j;
   }
}

Красивая визуализация: https://visualgo.net/en/heap

1 операцию мы умеем выполнять, просто спросив про корень.

Для 2 операции мы меняем последний элемент кучи и корень, а затем уменьшаем размер кучи и вызываем Down для корня.

3 операция - просто добавление элемента конец в кучи, а затем вызываем для него Up.