Куча¶
Подвешенное дерево - дерево, у которого есть корень.
Двоичная Куча - такое подвешенное дерево, для которого выполнены три условия:
1) Значение в любой вершине не меньше, чем значения её потомков.
2) У любой вершины не более двух сыновей.
3) Слои заполняются последовательно слева направо сверху вниз.
Давайте обозначим как h высоту кучи.
Куча также умеет 3 основные операции :
1) найти минимум за $O(1)$
2) удалить минимум за $O(h)$
3) добавление нового ключа в кучу за $O(h)$
Так как куча всегда состоит из нескольких слоев заполненых полностью и одного частично и каждый слой содержит в два раза больше вершин, чем предыдущий, то можно понять, что высота дерева будет не больше $O(log(N))$.
Теперь давайте поговорим о том, как же реализовать такую структуру.
Хранить кучу мы будем в виде массива, где у корня индекс равен $1$, и у вершины $n$ индексы ее потомков - $2 n$ и $2 n + 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.
Теоретическое задание¶
Дана куча из рисунка сверху, вам даны 3 запроса, нарисуйте как выглядит куча после каждого запроса:
- добавить число 125
- удалить максимальное
- вывести максимальное
В с++ куча реализована в STL в библиотеке <queue> :
priority_queue<type> Q;
Q.pop();
Q.push();
Q.top();
Практическое задание¶
В контесте на информатиксе на эту тему первые 5 задач.
Сортировка¶
На самом первом занятии вы ознакомились с квадратичными алгоритмами сортировки и сортировкой слияниями, а сейчас я вам расскажу гораздо более интересные сортировки.
Сортировка кучей¶
Только что мы с вами познакомились с кучей. Благодаря ей можно отсортировать числа по возрастанию: просто вставить все числа в кучу, а затем $N$ раз достать минимум. Работает это за $O(NlogN)$ (так как мы $N$ раз вставляем и удаляем элемент, а обе эти операции работают за логарифм).
Практическое задание¶
(6 задача)
Быстрая сортировка¶
Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент, все элементы, которые меньше его кидаем в левую часть, остальные в правую, а затем рекурсивно спускаемся в обе части.
void quicksort(int l, int r){
if (l < r){
int index = (l + r) / 2; /* index - индекс опорного элемента для
начала сделаем его равным середине отрезка*/
index = divide(l, r, index); /* divide - функция разбивающие элементы
на меньшие и больше/равные a[index],
при этом функция возвращает границу разбиения*/
quicksort(l, index);
quicksort(index + 1, r);
}
}
Давайте оценим асимптотику данной сортировки. На случайных данных она работает за $O(NlogN)$ , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна - одинаковые числа, а вторая - если вдруг середина - минимум или максимум.
Существуют несколько выходов из этой ситуации :
1) Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за $NlogN$.
2) Давайте делить массив не на две, а на три части(меньше, равны, больше).
3) Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент.
Теоретическое задание¶
Вывести оптимальные числа (при которых алгоритм работает быстрее всего) на всех этапах массива (8, 3, 2, 5, 4, 6, 7, 1).
Поиск $k$-ой порядковой статистики за $O(N)$¶
Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.
Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая
1) количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.
2) количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.
3) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.
За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму $\sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}$ что в нашем случае это максимум равно $2 * N - 1$, то есть $O(N)$.
Также в с++ эта функция уже реализована :
nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);
Ссылка на контесты¶
Куча: https://informatics.msk.ru/mod/statements/view.php?id=33379
Быстрая сортировка: http://ejudge.algocode.ru/cgi-bin/new-client?contest_id=5001
Практический контест: https://codeforces.com/group/g92L0id9Yb/contest/237751