Двоичная куча
Содержание
Определение
Определение: |
Двоичная куча или пирамида — такое двоичное подвешенное дерево, для которого выполнены следующие три условия:
|
Удобнее всего двоичную кучу хранить в виде массива
, у которого нулевой элемент, — элемент в корне, а потомками элемента являются и . Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть , где — количество узлов дерева.Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).
Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за
. Двоичные кучи — частный случай приоритетных очередей.Базовые процедуры
Восстановление свойств кучи
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры
function siftDown(i : int): if 2 * i + 1 <= A.heap_size //_ — количество элементов в куче left = A[2 * i + 1] // левый сын else left = inf if 2 * i + 2 <= A.heap_size right = A[2 * i + 2] // правый сын else right = inf if left == right == inf return if right <= left && right < A[i] swap(A[2 * i + 2], A[i]) siftDown(2 * i + 2) if (left < A[i]) swap(A[2 * i + 1], A[i]) siftDown(2 * i + 1)
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией
.Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем
function siftUp(i : int): if i == 0 return // мы в корне if A[i] < A[i / 2] swap(A[i], A[i / 2]) siftUp(i / 2)
Извлечение минимального элемента
Выполняет извлечение минимального элемента из кучи за время
. Извлечение выполняется в четыре этапа:- Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
- Последний элемент копируется в корень, после чего удаляется из кучи.
- Вызывается для корня.
- Сохранённый элемент возвращается.
T extractMin(): T min = A[0] A[0] = A[A.heap_size - 1] A.heap_size = A.heap_size - 1 siftDown(0) return min
Добавление нового элемента
Выполняет добавление элемента в кучу за время
. Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры .
function insert(key : T): A.heap_size = A.heap_size + 1 A[A.heap_size - 1] = key siftUp(A.heap_size - 1)
Построение кучи за O(N)
Определение: |
-куча — это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно потомков. |
Дан массив Требуется построить -кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать для каждого). Временная оценка такого алгоритма . Однако можно построить кучу еще быстрее — за .
Представим, что в массиве хранится дерево ( корень, а потомками элемента являются ). Сделаем для вершин, имеющих хотя бы одного потомка, начиная с конца(от до ) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
Лемма: |
На выходе получим искомую кучу. |
Доказательство: |
При вызове | для вершины, ее поддерево является кучей, после выполнения поддерево с этой вершиной будет являться кучей. Значит после выполнения всех получится куча.
Лемма: | ||||||
Время работы этого алгоритма . | ||||||
Доказательство: | ||||||
Число вершин на высоте в куче из элементов не превосходит . Высота кучи не превосходит . Обозначим за высоту дерева, тогда время построения не превосходит
Докажем вспомогательную лемму о сумме ряда.
| ||||||