Содержание¶

О чем мы сегодня будем говорить¶

Основные понятия¶

В начало

Heap (куча, невозрастающая/неубывающая пирамида)¶

Бинарные деревья¶

Важные моменты¶

Используется не только в пирамиде, но и в бинарных деревьях поиска, красно-черных деревьях...

Можно представлять эту структуру данных по-разному. Мы будем использовать массив

Но "идеологически" это что-то вроде

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

Свойства пирамиды¶

Для всех $i$ , кроме корневого узла

Невозврастающая пирамида (max-heap):

H e a p [P a r e n t (i)] \geq H e a p [i]

$Heap[Parent(i)] \geq Heap[i]$

Неубывающая пирамида (min-heap):

H e a p [P a r e n t (i)] \leq H e a p [i]

$Heap[Parent(i)] \leq Heap[i]$

Пример невозрастающей пирамиды¶

Обратите внимание! Это _не_ бинарное дерево поиска!

Представление в виде массива¶

Мы будем представлять дерево в виде массива. Какие функции нам нужно определить для удобства работы?

В начало

Процедуры адресации¶

Необходимые процедуры для работы с пирамидой в виде массива:

1  Parent(i):
2      return Floor((i - 1) / 2)
3  
4  LeftChild(i):
5      return i * 2 + 1
6
7  RightChild(i):
8      return i * 2 + 2

Приведение массива к пирамиде¶

Внимание, рекурсия!¶

Несмотря на то, что мы взяли за основу массив, пирамида по своей сути рекурсивна
Можно предположить, что удобно применять процедуры рекурсивно
Если два дочерних дерева удовлетворяют свойствам пирамиды, возьмем верхушку дерева и приведем все дерево к пирамиде

Эту процедуру можно повторять "снизу вверх", сортируя дерево

Как это выглядит¶

Псевдокод процедуры¶

Эта процедура предпологает, что левая и правая "под-пирамиды" действительно являются пирамидами!

1  Drown(Heap, i, size):  // (Пирамида, индекс, ограничения на массив)
2      l := Left(i)
3      r := Right(i)
4      if l ≤ size and Heap[l] > Heap[r]  // первая проверка - выход за пределы
5          largest := l
6      else 
7          largest := i   
8      if r ≤ size and Heap[r] > Heap[largest]
9          largest := r
10     if largest != i
11         Swap(Heap, i, largest)
12         Drown(Heap, largest, size)  // рекурсия

Справка про size : нужен только затем, чтобы не трогать отсортированную часть

Создание пирамиды из массива¶

1  BuildHeap(Array):
2      for i := Floor((length(Array) - 1) / 2) downto 0
3          Drown(Array, i, size)

В начало

Heapsort, пирамидальная сортировка¶

Набросок алгоритма¶

Неотсортированный массив преобразовать в пирамиду.
Повторять, пока весь массив не будет отсортирован:

Забрать "верхушку" и поместить в "отсортированную" часть, заменив на последний неотсортированный элемент (~как в _selection sort_)

Превратить все, кроме отсортированной части, в пирамиду

Алгоритм пирамидальной сортировки¶

1  Heapsort(Array):
2      size := length(Array)
3      BuildHeap(Array)
4      for i := length(Array) - 1 downto 1
5          size := size - 1
6          Swap(Array, 0, i)
7          Drown(Array, 0, size)
</pre>
</font>
Пример¶


В начало

Сложность и корректность¶

Чтобы суметь корркетно рассчитать сложность алгоритма и убедиться, что он работает, докажем его корректность.

Корректность Drown¶

Инициализация: левая, правая части - пирамиды; само значение может отличаться.
Сохранение:
- если значение в узле максимально, все ок.
- иначе оно меняется с НАИБОЛЬШИМ из листьев. Для другой ветви свойтсва пирамиды выполнены
- для той, с которой обменялись - ситуация та же, что и при инициализации
Завершение:
- мы дошли до тривиальной структуры со свойством пирамиды - листа - остановка

Корректность BuildHeap¶

Инициализация: мы находимся в $\bigg\lfloor \dfrac{length(Array) - 1}{2} \bigg\rfloor$ , все листья тривиальны и соответсвуют требованиям.
Сохранение: все узлы с меньшими номерами, чем указанный, также являются пирмаидами. При понижении индекса мы гарантированно проводим процедуру Drown корректно
Завершение: каждый узел - вершина пирамиды; при этом исполнение завершится, так как каждую индекс декрементируется

Корректность Heapsort¶

Инициализация: давайте разберем вместе, какие есть шаги
Сохранение: ...
Завершение: ...

В начало

Кратко

BuildHeap: $O (n)$
Heapsort: $O (n log(n))$
Поскольку при $n \rightarrow \inf$ выбирается максимальная сложность, то сложность сортировки будет

O (n) + O (n l o g (n)) = m a x (O (n), O (n l o g (n)) = O (n l o g (n))

$O(n) + O(n log(n)) = max(O(n), O(n log (n)) = O(n log(n))$

Опереации с O-нотацией¶

При $n \rightarrow \inf$ функция $f$ относится к $O(g(x))$ , если $| f(x) | < C \cdot | g(x)|$ для некоторого $C$

То есть $f(x)$ растет не быстрее, чем $g(x)$

Правила использования:

$O(x^n) \cdot O(x^m) = O(x^{m+n})$
$O(x^n) + O(x^m) = O(x^{max(m, n)})$ при $n \rightarrow \inf$

Ассимптотическая сложность BuildHeap¶

Начнем с Drown¶

В следующем блоке кода проводится конечное количество сравнений и операций, $O(1)$ :

1      l := Left(i)
2      r := Right(i)
3      if l ≤ size and Heap[l] > Heap[r]  // первая проверка - выход за пределы
4          largest := l
5      else 
6          largest := i   
7      if r ≤ size and Heap[r] > Heap[largest]
8          largest := r
9      if largest != i
10         Swap(Heap, i, largest)

После этого мы смещаемся на "один уровень" в глубину пирамиды и вызываем процедуру рекурсивно.

Для пирамиды размера $n$ глубина равна $\lceil log_{2} (n) \rceil$

В дереве максимум $2^{k+1}- 1$ , минимум $2^k$ элементов при глубине k:

2^{k + 1} = 1 + \sum_{i = 0}^{k} 2^{i}

$2^{k+1} = 1 + \sum_{i=0}^{k} 2^i$

Сложность равна $O(log(n)) \cdot O (1) = O(log (n))$

Сложность процедуры BuildHeap¶

Чуть более сложно. Мы будем опираться на логарифмическую сложность Drown и коичество операций на каждом слое дерева. Пирамида обходится "снизу вверх", т.е. от листьев.
Поэтому лежащие ниже под-пирамиды уже соответсвуют свойствам пирамиды, и нужен только один вызов Drown на пару.

Вопросы:

Сколько "под-пирамид" с высотой h?
Сколько времени вычисляется каждая "под-пирамида"?

Ответы:

~ $\dfrac{n}{2^{h+1}}$ "под-пирамид"
каждая обрабатывается $O(h)$

Итак, сложность:

\sum_{h = 0}^{l o g_{2} (n)} \frac{n}{2^{h + 1}} \cdot O (h) = O (n \cdot \sum_{h = 0}^{l o g_{2} (n)} \frac{h}{2^{h + 1}})

$\sum_{h=0}^{log_{2}(n)} \dfrac{n}{2^{h+1}} \cdot O(h) = O \bigg(n \cdot \sum_{h=0}^{log_{2}(n)} \dfrac{h}{2^{h+1}}\bigg)$

Внутренняя сумма

\sum_{h = 0}^{l o g_{2} (n)} \frac{h}{2^{h + 1}} = O (1)

$\sum_{h=0}^{log_{2}(n)} \dfrac{h}{2^{h+1}} = O(1)$

А сложность

n \cdot O (1) = O (n) \cdot O (1) = O (n)

$n \cdot O(1) = O(n) \cdot O(1) = O(n)$

В начало

Ассимптотическая сложность Heapsort¶

Складывается из сложности BuildHeap и произведения количества элементов в массиве на сложность Drown:

O (n) + n \cdot O (l o g (n)) = O (n \cdot l o g (n))

$O(n) + n \cdot O(log (n)) = O(n \cdot log(n))$

В начало

Плюсы, минусы, применение¶

Плюсы¶

Работает быстро, скорость в худшем случае $O(n \cdot log(n))$
Не нужно допольнительной памяти - inplace
Структура данных пирамида может применяться для других задач

Минусы¶

Нестабильная сортировка
Не совсем простой алгоритм

Применение¶

Для гарантированной $O(n \cdot log(n))$ сортировки без выделения памяти
Для очереди с приоритетами, поиска порядковых статистик, алгоритмов, где нужна очередь с приоритетом, например, очередь на python, на Java
Сортировка в линуксе

В начало

Домашняя работа¶

Реализовать Drown - 1 балл
Реализовать BuildHeap - 1 балл
Реализовать алгоритм Heapsort - 1 балл
- Можно все inline и без отдельных процедур, тогда 3 балла, если все иделаьно работает
- Heapsort должен работать для получения зачета
Дополнительно 1: реализовать Drown через стек, а не через рекурсию - 1 балл
Дополнительно 2: реализовать удаление элемента с сохранением свойст пирамиды - 1 балл
Дополнительно 3: реализовать очередь с приоритетами при помощи heap, сравнить с тем, что было ранее сделано - без баллов, по своему желанию (т.к. нам сложно гарантировать быструю проверку)

В начало