Подвешенное дерево - дерево, у которого есть корень.
Двоичная Куча - такое подвешенное дерево, для которого выполнены три условия:
Значение в любой вершине не меньше, чем значения её потомков.
У любой вершины не более двух сыновей.
Слои заполняются последовательно слева направо сверху вниз.
Давайте обозначим как h высоту кучи.
Куча также умеет 3 основные операции :
найти минимум за \(O(1)\)
удалить минимум за \(O(h)\)
добавление нового ключа в кучу за \(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 задача)
Быстрая сортировка заключается в том, что на каждом шаге мы находим опорный элемент, все элементы, которые меньше его кидаем в левую часть, остальные в правую, а затем рекурсивно спускаемся в обе части.
https://visualgo.net/en/sorting
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)\) , так как каждый раз мы будем делить массив на две примерно равные части, то есть суммарно размер рекурсии будет около логарифма и при этом на каждом этапе рекурсии мы просмотрим не более, чем размер массива. Однако можно легко найти две проблемы, одна - одинаковые числа, а вторая - если вдруг середина - минимум или максимум.
Существуют несколько выходов из этой ситуации :
Давайте если быстрая сортировка работает долго, то запустим любую другую сортировку за \(NlogN\).
Давайте делить массив не на две, а на три части(меньше, равны, больше).
Чтобы избавиться от проблемы с максимумом/минимумом в середине, давайте брать случайный элемент.
###Теоретическое задание
Вывести оптимальные числа (при которых алгоритм работает быстрее всего) на всех этапах массива (8, 3, 2, 5, 4, 6, 7, 1).
Пусть дан массив \(A\) длиной \(N\) и пусть дано число \(K\). Задача заключается в том, чтобы найти в этом массиве \(K\)-ое по величине число, т.е. \(K\)-ую порядковую статистику.
Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая
количество чисел, меньше данного = \(k - 1\), тогда наше число - ответ.
количество чисел, меньше данного >= \(k\), тогда спускаемся рекурсивно в левую часть и ищем там ответ.
количество чисел, меньше данного < \(k\), спускаемся в правую ищем (\(k\) - левая - 1) - ое число.
За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму \(\sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}\) что в нашем случае это максимум равно \(2 * N - 1\), то есть \(O(N)\).
Также в с++ эта функция уже реализована :
nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);Рассказать, как работает алгоритм при k = 5 и массиве - (1, 8, 4, 6, 7, 5, 3, 2), опорный элемент - середина
3 задачи на еджадже. В 2 из них у вас будет проверяться код.
Также нужно порешать практический контест на codeforces.
Куча: 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