Куча(Очередь с приоритетами): различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Куча== Подвешенное дерево - дерево, у которого есть корень. Двоичная Куча - такое подвеш...») |
Глеб (обсуждение | вклад) |
||
Строка 68: | Строка 68: | ||
3 операция - просто добавление элемента конец в кучи, а затем вызываем для него Up. | 3 операция - просто добавление элемента конец в кучи, а затем вызываем для него Up. | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 13:46, 22 октября 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.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin