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

Пусть мы хотим поддерживать множество элементов и быстро выполнять на нём следующие операции: добавлять и удалять элементы, а также находить минимум.

Можно попытаться сделать это с помощью динамического массива или списка. Тогда мы сможем добавлять и удалять элементы за $O(1)$ (чтобы быстро удалить элемент из массива, поменяем его местами с последним элементом, после чего уменьшим длину массива на один). Однако быстро находить минимум не получится: можно пытаться поддерживать указатель на минимальный элемент, но после каждого удаления минимума новый минимум получится найти лишь перебором всех оставшихся элементов за $\Theta(n)$ (где $n$ - число элементов в множестве). Можно было бы поддерживать массив в отсортированном порядке (тогда минимум всегда будет в начале), но тогда не получится быстро добавлять или удалять произвольный элемент.

Двоичная куча (пирамида), binary heap - структура данных, которая позволяет добавлять и удалять элементы за $O(\log n)$, а также в любой момент иметь доступ к минимальному элементу в множестве за $O(1)$.

Определение

Двоичная куча из $n$ элементов - это массив $a$ с индексами от 1 до $n$, образующий двоичное дерево: для любого $1 < i \leqslant n$ родитель $i$-го элемента - это элемент с номером $\left\lfloor\frac{i}{2}\right\rfloor ;$ соответственно, для любого $1 \leqslant i \leqslant n$ дети $i$-го элемента имеют номера $2 i, 2 i+1$ (если элементы с такими номерами существуют).

При этом выполняется свойство кучи: значение любого элемента не меньше значения его родителя: $a[i] \geqslant a\left[\left\lfloor\frac{i}{2}\right]\right]$. Такую кучу также могут называть неубывающая пирамида. Аналогично, если $a[i] \leqslant a\left[\left\lfloor\frac{i}{2}\right]\right]$ - то невозрастающая пирамида.

Заметим, что отсортированный массив всегда является кучей. Но фиксированный набор элементов обычно можно упорядочить и многими другими способами так, что тоже получится куча.

Будем пользоваться терминами из теории графов. Элементы дерева (кучи) будем называть вершинами. Корень дерева - единственная вершина без родителя (в нашем случае это $a[1]$ ). Потомки вершины - это она сама, её дети, а также все их потомки; у листа (вершины без детей) потомков (кроме него самого) нет. Предок вершины $v$ - любая такая вершина $u$, что $v$ - потомок $u$. Поддерево вершины $v$ состоит из всех её потомков; $v$ - корень своего поддерева.

Иногда мы будем называть кучей не массив с индексами от 1 до $n$, а просто дерево, в котором свойство кучи выполняется для всех пар родитель-ребёнок. В этом смысле любое поддерево кучи тоже является кучей.

Глубина $x$ - количество вершин на пути от корня дерева до $x$ (все вершины являются потомками корня). Высота вершины $x$ - максимальное количество вершин на пути от $x$ до какого-либо её потомка. Высота дерева - максимум из высот вершин, то есть высота корня.

Глубина $i$-й вершины равна $\lfloor\log i\rfloor+1$, так как $i$ нужно поделить на два нацело $\lfloor\log i\rfloor$ раз, чтобы получить 1.

Высота корня - это максимум из глубин всех его потомков. Максимальная глубина у $n$-й вершины $-\lfloor\log n\rfloor+1$. Значит, высота кучи из $n$ элементов равна $\lfloor\log n\rfloor+1$.

Базовые операции

Научимся выполнять три простых операции: getMin() - поиск минимального элемента в куче, insert(x) - добавление нового элемента $x$ в кучу, и extractMin() - удаление минимума из кучи. Последние две операции будут пользоваться вспомогательными операциями $\operatorname{siftUp(i)~и~siftDown(i).~}$

Поиск минимума

Из определения кучи сразу же следует, что минимальный элемент всегда будет находиться в корне. Тогда просто вернём $a[1]$, время работы $-O(1)$.

1
2

getMin():
    return a[1]

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

Пусть свойство кучи “практически” выполняется: для некоторого $i$ известно, что $a[i]=x$ можно увеличить так, что массив $a$ станет кучей. Такую почти кучу можно “починить”, не меняя множество лежащих в ней значений, следующим образом: просто будем “поднимать” $x$ вверх, пока $x$ меньше значения в родителе.

1
2
3
4

siftUp(i):
    while i > 1 and a[i] < a[i / 2]:
        swap(a[i], a[i / 2])
        i /= 2
Свойства

Пусть известно, что $a[i]=x$ можно увеличить так, что массив $a$ станет кучей. Тогда после выполнения $\operatorname{siftUp}(i)$ массив $a$ станет кучей.

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

Докажем утверждение индукцией по $i$. База. Если $i=1$, то $a$ уже является кучей (если корень можно увеличить так, что он станет не больше детей, то он и сейчас не больше детей). siftUp(1) не меняет массив $a$.

Переход. Заметим сначала, что если $a$ уже является кучей, то $\operatorname{siftUp}(i)$ ничего не сделает, поэтому утверждение предложения верно.

Если $a$ не является кучей, то единственная пара родитель-ребёнок, для которой не выполняется свойство кучи - это $x=a[i]

После первой итерации цикла $x$ и $y$ поменяются местами: $y=a[i] > a\left[\left\lfloor\frac{i}{2}\right\rfloor\right]=x$. Заметим, что такой массив $a$ станет кучей, если значение $a\left[\left\lfloor\frac{i}{2}\right\rfloor\right]$ увеличить до $y$ (это равносильно увеличению $a[i]$ до $y$ в исходном массиве). Тогда, поскольку последующие действия siftUp эквивалентны рекурсивному вызову $\operatorname{siftUp}(i / 2)$, по индукции верно, что по завершении операции массив $a$ станет кучей.

Количество итераций цикла в siftUp(i) не превосходит глубины $i$-й вершины, то есть время работы оценивается как $O(\log i+1)$.

Чтобы добавить новый элемент $x$ в кучу размера $n$, запишем $x$ в $a[n+1]$ (мы предполагаем, что массив $a$ достаточно большого размера либо динамический). При этом $a$ мог перестать быть кучей, но $a[n+1]$ можно увеличить так, что $a$ снова станет кучей (например, сделав его больше всех остальных элементов), поэтому достаточно запустить от него siftUp. Получаем время работы $O(\log n)$.

1
2
3
4

insert(x):
    sz += 1 # sz - размер кучи
    a[sz] = x
    siftUp(sz)

Удаление минимума

Пусть известно, что $a[i]=x$ можно уменьшить так, что массив $a$ станет кучей. Такую почти кучу тоже можно “починить”: будем “опускать” $x$ вниз, пока $x$ больше хотя бы одного из значений в детях, при этом будем менять $x$ местами с тем ребёнком, значение в котором меньше.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

siftDown(i):
    while 2 * i <= sz:
        j = 2 * i
        if 2 * i + 1 <= sz and a[2 * i + 1] < a[2 * i]:
            j = 2 * i + 1
        # j - номер минимального по значению ребёнка i-й вершины
        if a[j] >= a[i]:
            break
        swap(a[j], a[i])
        i = j
Свойства

Пусть известно, что $a[i]=x$ можно уменьшить так, что массив $a$ размера $n$ станет кучей. Тогда после выполнения siftDown(i) массив $a$ станет кучей.

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

Докажем утверждение “обратной” индукцией по $i$. База. Если $i>2 n$, то $a$ уже является кучей (если лист можно уменьшить так, что он станет не меньше родителя, то он и сейчас не меньше родителя). siftDown(i) в таком случае не поменяет массив $a$.

Переход. Заметим сначала, что если $a$ уже является кучей, то siftDown(i) ничего не сделает, поэтому утверждение предложения верно.

Если $a$ не является кучей, то свойство кучи может не выполняться только для тех пар родитель-ребёнок, в которых $a[i]$ является родителем. Пусть $j$ - номер минимального по значению из детей $i$-й вершины, $y=a[j]

После первой итерации цикла $x$ и $y$ поменяются местами: $y=a[i] < a[j] = x$. Заметим, что такой массив $a$ станет кучей, если значение $a[j]$ уменьшить до $y$ (это равносильно уменьшению $a[i]$ до $y$ в исходном массиве). Тогда, поскольку последующие действия siftDown эквивалентны рекурсивному вызову $\operatorname{siftDown(j)}$, по индукции верно, что по завершении операции массив $a$ станет кучей.

Количество итераций цикла в $\operatorname{siftDown(i)}$ не больше высоты $i$-й вершины, поэтому время работы оценивается как $O(\log n-\log i+1)=O\left(\log \frac{n}{i}+1\right)$, или, более грубо, $O(\log n)$.

Чтобы удалить минимум из кучи размера $n$, поменяем местами $a[1]$ и $a[n]$, и уменьшим размер кучи на один. Теперь в $a[1]$ находится возможно не минимальный элемент, но его можно уменьшить так, что $a$ опять станет кучей (например, сделать его меньше всех остальных элементов). Тогда достаточно запустить $\operatorname{siftDown(1)}$. Получаем время работы $O(\log n)$.

1
2
3
4
5

extractMin():
    swap(a[1], a[sz])
    sz -= 1
    if sz >= 1: # если куча непуста
        siftDown(1)

Построение кучи

Самый простой способ построить кучу из $n$ элементов - начать с пустой кучи, и добавлять элементы по одному. В худшем случае (если все вызовы $\operatorname{siftUp}$ будут подниматься до корня, то есть если элементы добавляются в убывающем порядке) получим время работы $\Theta(n \log n)$.

Можно построить кучу быстрее: сложим элементы в массив в произвольном порядке, после чего поочерёдно запустим siftDown от всех элементов, не являющихся листьями, в порядке убывания их номеров.

1
2
3
4

build(a, n):
    sz = n
    for i = (n / 2)..1:
        siftDown(i)
Лемма

После выполнения $\operatorname{build}$ массив $a$ станет кучей.

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

Докажем “обратной” индукцией по $i$, что после запуска $\operatorname{siftDown(i)}$ поддерево $i$-й вершины является кучей.

База. $i>\left\lfloor\frac{n}{2}\right\rfloor$ (на самом деле для таких $i$ мы не вызываем $\operatorname{siftDown}$, потому что он всё равно ничего не сделает). В этом случае поддерево состоит из одной вершины, поэтому утверждение верно.

Переход. По предположению индукции, поддеревья детей $i$-й вершины являются кучами. Значит, $a[i]$ можно уменьшить так, что и поддерево $i$-й вершины станет кучей (например, сделав $a[i]$ меньше значений в детях). Тогда после запуска $\operatorname{siftDown(i)}$ поддерево $i$-й вершины станет кучей.

Время работы $\operatorname{build}$ тоже складывается из $O(n)$ запусков функций, каждая из который работает за $O(\log n)$. Однако оценка времени работы $O(n \log n)$ в этом случае не является точной.

Теорема

Время работы $\operatorname{build}$ есть $\Theta(n)$.

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

Воспользуемся более точной оценкой времени работы $\operatorname{siftUp}$: пусть $\lfloor\log n\rfloor=k$, то есть $2^{k} \leqslant n < 2^{k+1}$. Высоту один имеет $n-2^{k}+1 \leqslant 2^{k}$ вершин. Высоту $1 < h \leqslant k+1$ имеет $2^{k+2-h}-2^{k+1-h}=2^{k+1-h}$ вершин. Тогда время работы $\operatorname{build}$ есть

$$ \begin{aligned} & O\left(\sum_{h=1}^{k+1} 2^{k+1-h} \cdot h\right)=O\left(n \cdot \sum_{h=1}^{k+1} \frac{h}{2^{h}}\right)=O\left(n \cdot \sum_{j=1}^{k+1} \sum_{h=j}^{k+1} \frac{1}{2^{h}}\right)= \\ & =O\left(n \cdot \sum_{j=1}^{k+1} \frac{1}{2^{j}} \cdot \frac{1}{1-\frac{1}{2}}\right)=O\left(n \cdot \frac{1}{1-\frac{1}{2}} \cdot \frac{1}{1-\frac{1}{2}}\right)=O(n) \end{aligned} $$

Heapsort

С помощью двоичной кучи можно отсортировать массив за $O(n \log n)$ : построим кучу на массиве, после чего $n$ раз извлечём минимум. Если в корне кучи хранится максимум, а не минимум (свойство кучи в таком случае меняется на противоположное: любой элемент не больше своего родителя), то при извлечении максимума из кучи размера $k$ он как раз оказывается на $k$-й позиции в массиве, поэтому алгоритму даже не нужна дополнительная память.

1
2
3
4

heapSort(a, n):
    build(a, n) # строим кучу, в корне которой хранится максимум
    for i = 0..(n - 1):
            extractMax()

✍️ Heapsort не является стабильной сортировкой.

Очередь с приоритетами

Очередь с приоритетами (priority queue) отличается от обычной очереди тем, что у каждого элемента есть приоритет, и извлекается не тот элемент, что был добавлен в очередь раньше всех, а элемент с максимальным приоритетом. Встроенная в C++ реализация очереди с приоритетами - std::priority_queue.

Потребность в использовании очереди с приоритетами возникает, например, при планировании задач в многозадачных операционных системах (процессы с большим приоритетом нужно выполнить раньше). Также очередь с приоритетами используется во многих алгоритмах, некоторые из которых нам ещё встретятся.

Очередь с приоритетами легко реализовать с помощью двоичной кучи с максимумом в корне: будем сравнивать элементы по их приоритету.

Удаление или изменение произвольного элемента

При использовании очереди с приоритетами часто хочется иметь возможность делать дополнительные операции: менять значение приоритета у объекта, лежащего в очереди, или удалять из очереди произвольный объект, не обязательно с максимальным приоритетом. Покажем, что двоичная куча поддерживает такие операции.

Если приоритет объекта не максимален, то сложно быстро понять, где именно в куче он находится. Поэтому когда возникает потребность в таких операциях, обычно для каждого объекта дополнительно поддерживается ссылка на его позицию в куче (обычно это просто номер этой позиции), а для каждой позиции в куче поддерживается ссылка на объект, который находится в этой позиции. Так, если объекты пронумерованы числами от $1$ до $n$, можно поддерживать массив pos, в $i$-й ячейке которого будет храниться позиция в куче элемента с номером $i$. При перестройке кучи этот массив несложно пересчитывать.

Итак, пусть мы хотим удалить объект из кучи $a$ размера $n$, при этом мы знаем, что сейчас он находится на позиции $i$. Поступим так же, как и при удалении максимума: поменяем $i$-й элемент местами с последним, и уменьшим размер кучи. После этого $a$ может перестать быть кучей, но $i$-й элемент можно либо увеличить, либо уменьшить так, что $a$ снова станет кучей (например, можно вернуть старое значение $i$-го элемента). Значит после вызова $\operatorname{siftUp(i)}$ или $\operatorname{siftDown(i)}$ $a$ снова станет кучей. Если мы вызовем обе операции, то одна из них “починит” кучу, а вторая ничего не сделает. Время работы $O(\log n)$.

1
2
3
4
5
6

delete(i):
    swap(a[i], a[sz])
    sz -= 1
    if i <= sz:
        siftUp(i)
        siftDown(i)

Точно так же можно менять значение приоритета у произвольного объекта. Пусть объект находится в куче в позиции $i$, тогда поменяем значение приоритета и снова запустим $\operatorname{siftUp(i)}$, $\operatorname{siftDown(i)}$. Это работает ровно по тем же причинам, что и в случае удаления. Время работы снова $O(\log n)$.

1
2
3
4

change(i, x):
    a[i] = x
    siftUp(i)
    siftDown(i)

✍️ Существуют и более сложные кучи, обладающие различными дополнительными полезными свойствами. Фибоначчиевы кучи (Fredman, Tarjan, 1987) известны тем, что позволяют в среднем за $O(1)$ не только находить минимум, но и добавлять новый элемент, а также уменьшать значение элемента. Удаление работает в среднем за $O(\log n)$. Использование фибоначчиевой кучи позволяет улучшить теоретическую оценку времени работы некоторых алгоритмов. Проблема в том, что из-за сложности реализации и большой константы в оценке времени работы на практике фибоначчиевы кучи, как правило, работают не быстрее обычных, поэтому практически не применяются и имеют скорее теоретическую ценность.