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

Определение

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

Двоичная куча или пирамида (англ. Binary heap) — такое двоичное подвешенное дерево, для которого выполнены следующие три условия: Значение в любой вершине не меньше (если куча для максимума), чем значения её потомков. На [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]. Они являются частным случаем приоритетных очередей.

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

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры [math] \mathrm {siftDown} [/math] (просеивание вниз) и [math] \mathrm {siftUp} [/math] (просеивание вверх).

siftDown

Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftDown} [/math].

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

function siftDown(i : int):
    while 2 * i + 1 < a.heapSize     // heapSize — количество элементов в куче
        left = 2 * i + 1             // left — левый сын
        right = 2 * i + 2            // right — правый сын
        j = left
        if right < a.heapSize and a[right] < a[left]
            j = right
        if a[i] <= a[j]
            break
        swap(a[i], a[j])
        i = j

siftUp

Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftUp} [/math].

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

function siftUp(i : int):
    while a[i] < a[(i - 1) / 2]     // i [math]==[/math] 0 — мы в корне
        swap(a[i], a[(i - 1) / 2])
        i = (i - 1) / 2

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

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

1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
2. Последний элемент копируется в корень, после чего удаляется из кучи.
3. Вызывается [math] \mathrm {siftDown} [/math] для корня.
4. Сохранённый элемент возвращается.

int extractMin():
    int min = a[0]
    a[0] = a[a.heapSize - 1]
    a.heapSize = a.heapSize - 1
    siftDown(0)
    return min

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

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

function insert(key : int):
    a.heapSize = a.heapSize + 1
    a[a.heapSize - 1] = key
    siftUp(a.heapSize - 1)

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

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

[math]D[/math]-куча — это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно [math]d[/math] потомков.

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

Представим, что в массиве хранится дерево ([math]a[0] - [/math] корень, а потомками элемента [math]a[i][/math] являются [math]a[di+1]...a[di+d][/math]). Сделаем [math] \mathrm {siftDown} [/math] для вершин, имеющих хотя бы одного потомка: от [math]\dfrac{n}{d}[/math] до [math]0[/math],— так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.

Лемма:

На выходе получим искомую кучу.

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

[math]\triangleright[/math]

При вызове [math] \mathrm {siftDown} [/math] для вершины, ее поддеревья являются кучами. После выполнения [math] \mathrm {siftDown} [/math] эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех [math] \mathrm {siftDown} [/math] получится куча.

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

Число вершин на высоте [math]h[/math] в куче из [math]n[/math] элементов не превосходит [math] \left \lceil \frac{n}{d^h} \right \rceil [/math]. Высота кучи не превосходит [math] \log_{d}n [/math]. Обозначим за [math] H [/math] высоту дерева, тогда время построения не превосходит [math] \sum_{h = 1}^H \limits\frac{n}{d^h} \cdot d [/math] [math] \cdot h [/math] [math] = n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{d^h}. [/math] Докажем вспомогательную лемму о сумме ряда. Лемма: [math] {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . [/math] Доказательство: [math]\triangleright[/math] Обозначим за [math]s[/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]\triangleleft[/math] Подставляя в нашу формулу результат леммы, получаем [math]n[/math] [math]\cdot (\frac {d}{d - 1})^2 [/math] [math] \leqslant 4 \cdot n [/math] [math]=O(n).[/math]

[math]\triangleleft[/math]

Псевдокод алгоритма:

function buldHeap():
    for i = a.heapSize / 2 downto 0
        siftDown(i)

Слияние двух куч

Даны две кучи [math]a[/math] и [math]b[/math], размерами [math]n[/math] и [math]m[/math], требуется объединить эти две кучи.

Наивная реализация

Поочередно добавим все элементы из [math]b[/math] в [math]a[/math]. Время работы — [math]O(m \log(n+m))[/math].

function merge(a, b : Heap):
    while b.heapSize > 0  
        a.insert(b.extractMin())

Реализация с помощью построения кучи

Добавим все элементы кучи [math]b[/math] в конец массива [math]a[/math], после чего вызовем функцию построения кучи. Процедура выполняется за время [math]O(n + m)[/math].

function merge(a, b : Heap):
    for i = 0 to b.heapSize - 1  
        a.heapSize = a.heapSize + 1
        a[a.heapSize - 1] = b[i]
    a.heapify()

Поиск k-ого элемента

Требуется найти [math]k[/math]-ый по величине элемент в куче.

1. Создаем новую кучу, в которой будем хранить пару [math]\langle \mathtt{value}, \mathtt{index} \rangle[/math], где [math]\mathtt{value}[/math] — значение элемента, а [math]\mathtt{index}[/math] — индекс элемента в основном массиве, и добавляем в нее корень кучи.
2. Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг [math]k - 1[/math] раз.
3. В корне новой кучи будет находиться ответ.

Время работы алгоритма — [math]O(k \log k)[/math].

При [math]n \lessapprox k \log k [/math] выгоднее запускать поиск k-ой порядковой статистики.

Пример при [math]k = 5[/math], красные — уже удаленные из кучи элементы, зеленые находятся в куче, а голубые — еще не рассмотрены.

См. также

• Биномиальная куча
• Фибоначчиева куча
• Левосторонняя куча

Источники информации

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