Двоичная куча

Определение

Определение:

Двоичная куча или пирамида — такое двоичное подвешенное дерево, для которого выполнены следующие три условия: Значение в любой вершине не меньше, (если куча для максимума), чем значения её потомков. На [math]i[/math]-ом слое [math]2^i[/math] вершин, кроме последнего. Слои нумеруются с нуля. Последний слой заполнен слева направо (как показано на рисунке)

Пример кучи для максимума

Удобнее всего двоичную кучу хранить в виде массива [math]A[0..n-1][/math], у которого нулевой элемент, [math]A[0][/math] — элемент в корне, а потомками элемента [math]A[i][/math] являются [math]A[2i+1][/math] и [math]A[2i+2][/math]. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть [math]O(\log{N})[/math], где [math]N[/math] — количество узлов дерева.

Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за [math]O(\log{N})[/math]. Двоичные кучи — частный случай приоритетных очередей. Приоритетная очередь — это структура данных, которая позволяет хранить пары (значение и ключ) и поддерживает операции добавления пары, поиска пары с минимальным ключом и ее извлечение.

Базовые процедуры

Восстановление свойств кучи

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры sift_down (просеивание вниз) и sift_up (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией sift_down(i). Работа процедуры: если [math]i[/math]-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами [math]i[/math]-й элемент с наименьшим из его сыновей, после чего выполняем sift_down() для этого сына. Процедура выполняется за время [math]O(\log{N})[/math].

sift_down(i)
 // heap_size - количество элементов в куче
 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])
   sift_down(2 * i + 2)  
 if (left < A[i]) 
   swap(A[2 * i + 1], A[i])
   sift_down(2 * i + 1) 

Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией sift_up(i).

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем sift_up для этого отца. Иными словами, слишком большой элемент всплывает наверх. Процедура выполняется за время [math]O(\log{N})[/math].

sift_up(i)
if (i == 0) return //Мы в корне
 if (A[i] < A[i / 2])
   swap(A[i], A[i / 2]);
   sift_up(i / 2)

Извлечение минимального элемента

Выполняет извлечение минимального элемента из кучи за время [math]O(\log{N})[/math]. Извлечение выполняется в четыре этапа:

1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
2. Последний элемент копируется в корень, после чего удаляется из кучи.
3. Вызывается sift_down(i) для корня.
4. Сохранённый элемент возвращается.

extract_min()
 min = A[0]
 A[0] = A[A.heap_size - 1]
 A.heap_size = A.heap_size - 1
 sift_down(0)
 return min

Добавление нового элемента

Выполняет добавление элемента в кучу за время [math]O(\log{N})[/math]. Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры sift_up.

insert(key)
 A.heap_size = A.heap_size + 1
 A[A.heap_size - 1] = key
 sift_up(A.heap_size - 1)

Построение кучи за O(N)

Дан массив [math] A[0.. n - 1]. [/math] Требуется построить кучу с минимумом в корне. Наиболее очевидный способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы (сделать sift_down). Временная оценка такого алгоритма [math] O(N\log{N})[/math]. Однако можно построить кучу еще быстрее — за [math] O(N) [/math]. Представим, что в массиве хранится дерево ( [math]A[0][/math] — корень, а потомками элемента [math]A[i][/math] являются [math]A[2i+1][/math] и [math]A[2i+2][/math]). Делаем sift_down для вершин имеющих хотя бы одного потомка (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). На выходе получим искомую кучу.

Лемма:

Время работы этого алгоритма [math] O(N) [/math].

Доказательство:

[math]\triangleright[/math]

Число вершин на высоте [math]h[/math] в куче из [math]n[/math] элементов не превосходит [math] \left \lceil \frac{n}{2^h} \right \rceil [/math]. Высота кучи не превосходит [math] \log_{2} n [/math]. Обозначим за [math] H [/math] высоту дерева, тогда время построения не превосходит [math] \sum_{h = 1}^H \limits\frac{n}{2^h}[/math] [math] \cdot h [/math] [math]= n \cdot {\sum_{h = 1}^H \limits}\frac{h}{2^h}. [/math] [math] {\sum_{h = 1}^\infty \limits}\frac{h}{2^h} = 2 [/math] (известная сумма из матанализа) Обозначим сумму ряда за [math] S [/math]. Заметим что, [math] \frac{n}{2^n} = \frac{1}{2} \cdot \frac{n - 1}{2 ^{n - 1}} + \frac{1}{2^n} [/math] Получается [math] S = \frac{1}{2} \cdot S + 1 [/math] (так как [math]n \gt 0[/math]). Получаем, что сумма ряда равна 2. Откуда и получаем оценку [math] O(N) [/math].

[math]\triangleleft[/math]

Также можно обобщить на случай [math] d-[/math] кучи [math](d- [/math] куча это куча в которой не 2 потомка, а [math] d [/math] потомков). Все операции, которые делались c бинарной кучей, допустимы и для [math]d[/math] - кучи. Посчитаю время построения [math] d[/math] - кучи. В этом случае время работы не превзойдет [math]N \cdot d [/math] [math] \cdot {\sum_{i = 1}^H \limits}\frac{i}{d^i} .[/math]

Здесь появился множитель [math] d [/math] из-за того, что поиск минимума в sift_down происходит за [math] d [/math].

Аналогичным образом посчитаю ряд [math] {\sum_{n = 1}^\infty \limits}\frac{n}{d^n} [/math]

[math] \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. [/math]

[math]{\sum_{n = 1}^\infty \limits}\frac{1}{d^n} [/math] это сумма бесконечной убывающей геометрической прогрессии ее сумма равна [math] \frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1} [/math]

Получаю [math] S [/math] [math]= \frac{1}{d}[/math] [math]\cdot S[/math] [math] + \frac{1}{d - 1}. [/math] Откуда [math] S[/math] [math] = \frac{d}{(d - 1)^2}. [/math]

Подставляя в формулу для суммы получаю [math] N [/math] [math]\cdot (\frac {d}{d - 1})^2 [/math] [math] \lt 5 \cdot N [/math].

Получаю время работы [math] O(N) [/math]

Источники

• Двоичная куча — Wikipedia
• Очередь с приоритетом — Wikipedia