Двоичная и d-арная куча

Про приоритетные очереди

С помощью линейных структур нельзя реализовать эффективную приоритетную очередь.

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

Давайте создадим бинарное дерево, в котором каждая вершина будет больше своих потомков. При этом, для достижения минимальной высоты $\lfloor \log_2 n \rfloor + 1$ , сделаем дерево полным.

Полное бинарное дерево можно хорошо хранить в массиве h длины $n$ (индексация, напомню, с $0$ ). Тогда у элемента с индексом $i$ детьми являются элементы с индексами $2i+1$ и $2i+2$ , а родителем — элемент с индексом $\lfloor (i-1)/2 \rfloor$ .

По нашему построению видно, что максимальный элемент в куче имеет индекс $0$ , а минимальный элемент находится в одном из листьев. А так же для всех элементов выполнено «свойство кучи»:

\code{h}[i] \ge \code{h} \bigl[ \lfloor (i-1)/2 \rfloor \bigr] \quad \text{для всех}~ i

Теперь мы можем производить какие-то операции с кучей. А именно, вставлять элементы, изменять элементы и извлекать минимум (про тонкости реализации позже).

После изменения элементов свойство кучи может нарушиться. Поэтому нам надо научиться быстро восстанавливать его.

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

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

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

Просеивание вниз (shift down).

Если просеиваемый элемент меньше, чем его дети, то меняем его с наибольшим из его детей.
Продолжаем его просеивать, пока он не встанет на нормальное место или пока он не станет листом.

function shift_down(mutable array h, int i):
    const int n = length(h)

    while 2 * i + 1 < n:
        left = 2 * i + 1
        right = 2 * i + 2

        if right < n and h[right] > h[left]:
            j = right
        else:
            j = left

        break if h[i] >= h[j]

        swap h[i], h[j]
        i = j

Если просеиваемый вниз элемент находился на высоте $h$ , то выполнение операции потребует не более $h-1$ обменов и не более $2h-2$ сравнений. Константа $2$ вылезает потому, что сравниваем мы каждым ребенком.

Просеивание вверх (shift up).

Если просеиваемый элемент меньше, чем его родитель, то меняем его с его родителем.
Продолжаем его просеивать, пока он не встанет на нормальное место или пока он не станет корнем.

Здесь нет никаких ветвлений, в отличие от просеивания вниз, поэтому код будет более красивым

function shift_up(mutable array h, int i):
    while h[i] > h[(i - 1) / 2]:
        swap h[i], h[(i - 1) / 2]
        i = (i - 1) / 2

Обе операции работают за время $O(\text{высота кучи}) = O(\log n)$ .

Вставка

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

Извлечение максимума

При извлечении минимума можно воспользоваться примерно тем же трюком, что и со вставкой. Поместим на место корня элемент $-\oo$ , который гарантированно меньше любого другого элемента. Теперь осталось просто просеять вниз этот элемент.

Можно обойтись и без введения особого элемента, если вспомнить, что листы — наименьшие элементы в куче. Можно на место корня ставить не $-\oo$ , а какой-то лист, например последний. Эффект от просеивания этого элемента вниз будет точно таким же, как и от просеивания $-\oo$ : свойство кучи сохранено, максимум извлечён.

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

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

Но в куче очень много беспорядков. Можно этим воспользоваться. Построить кучу из массива может операция heapify.

Представим, что в исходном массиве уже записано полное бинарное дерево. Оно не удовлетворяет свойству кучи. Давайте просеем вниз все узлы, которые имеют хотя бы одного ребёнка. При этом будем просеивать снизу вверх, то есть начнем с элемента на позиции $\lfloor n/2 \rfloor$ , а закончим корнем, который находится на позиции $1$ .

В итоге мы из массива получим нормальную кучу. До просеивания какого-то узла оба его поддерева удовлетворяли свойству кучи. После просеивания этого узла он вместе со своими поддеревьями будет образовывать кучу. Значит, после просеивания всех узлов у нас получится куча.

function heapify(mutable array h):
    const int n = length(h)
    
    for int i = (n-1)/2; i >= 0; i--:
        sift_down(h, i)

Время работы этой операции $O(n)$ .

Число вершин на высоте $h$ не более $\lceil n / 2^h \rceil$ . Для каждой из них будет вызвана операция просеивания вниз, которая потребует не более $h$ обменов и не более $2h$ сравнений. Значит, количество сравнений в операции heapify равно

\sum\limits_{h=1}^{\lfloor \log_2 n \rfloor + 1} \Bigl\lceil \frac{n}{2^h} \Bigr\rceil \cdot (2h-2) = 2n \sum\limits_{h=1}^{\lfloor \log_2 n \rfloor + 1} \frac{h-1}{2^h} = 4n + O(\log n)

А количество обменов в $2$ раза меньше, $2n + O(\log n)$ .

Анализ алгоритмов на куче

Одна из самых важных характеристик кучи — размеры её поддеревьев. Просто так получить все значения, к сожалению нельзя. Проблемы возникают только из-за того, что куча — полное дерево, но не всегда абсолютно сбалансированное.

В куче есть «особый путь», соединяющий корень кучи с последним листом. На картинке я его отметил красным.

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

Все неособые поддеревья являются абсолютно сбалансированными, значит их размер всегда равен $2^k - 1$ . А количество неособых поддеревьев очень легко вычисляется:

\text{неособых деревьев размера}~ 2^k-1 ~\text{ровно} \left\lfloor \frac{n - 2^{k-1}}{2^k} \right\rfloor ~\text{штук}

Осталось разобраться с особыми узлами. Пусть двоичное представление числа $n$

n = \bigl( b_{h} \, b_{h-1} \, b_{h-2} \, \dotsm \, b_2, b_1, b_0 \bigr)_2 \quad \text{где}~ h = \lfloor \log_2 n \rfloor

Тогда размеры особых поддеревьев можно явно выразить через эти цифры. Напишу сверху вниз

\bigl( 1 \, b_{h-1} \, b_{h-2} \, \dotsm \, b_2 \, b_1 \, b_0 \bigr)_2 \quad \bigl( 1 \, b_{h-2} \, \dotsm \, b_2 \, b_1 \, b_0)_2 \quad \cdots \quad \bigl(1 \, b_1 \, b_0 \bigr)_2 \quad \bigl( 1 \, b_0 \bigr)_2 \quad 1_2

Теперь мы можем посчитать количество всевозможных куч на $n$ элементах. Пусть $s_v$ — размер поддерева с корнем в $v$ . Тогда всего куч

\frac{n!}{s_1 \cdot s_2 \cdot s_3 \dotsm s_{n-1} \cdot s_n} = n! \bigg/ \prod\limits_{v} s_v

Пирамидальная сортировка

С помощью кучи можно реализовать прекрасный алгоритм сортировки, называемый пирамидальной сортировкой. Названия действительно не совпадают. По-русски куча это пирамида, но такое название приоритетной очереди не прижилось в профессиональных кругах. А сортировка, работающая с помощью кучи, по-прежнему называется пирамидальной. В английском языке все хорошо: структура данных heap, сортировка heap sort.

Нам дали массив, который нужно отсортировать. Применим операцию heapify, превратив массив в кучу на максимум за $4n + O(\log n)$ сравнений и $2n + O(\log n)$ обменов. Затем будем извлекать максимум из кучи, пока та не кончится.

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

function heap_sort(mutable array h):
    int n = length(h)

    heapify()

    repeat n times:
        swap h[0] = h[n-1]
        n -= 1
        shift_down(0)

Если в алгоритм пирамидальной сортировки даётся случайная перестановка чисел $(1, 2, \dotsc, n)$ , то при heapify может равновероятно получиться любая из $n! \bigm/ \prod\limits_{v} s_v$ возможных куч.

Построение кучи, как мы уже выяснили, требует $4n + O(\log n)$ сравнений и $2n + O(\log n)$ обменов. После этого мы $n$ раз извлекаем максимум, который находится в корне, на высоте $\lfloor \log_2 n \rfloor + 1$ . Эта операция просто вызывает просеивание вниз, а значит требует $\lfloor \log_2 n \rfloor$ обменов и $2 \lfloor \log_2 n \rfloor$ сравнений. В итоге пирамидальная сортировка требует

\text{максимум} \quad 2 n \lfloor \log_2 n \rfloor + 4n + O(\log n) ~~\text{сравнений} \quad \text{и} \quad n \lfloor \log_2 n \rfloor + 2n + O(\log n) ~~\text{обменов}

Огрубив, говорим, что пирамидальная сортировка работает за $\Theta(n \log n)$ .

$d$ -арная куча

Есть смысл рассматривать не только бинарные деревья для представления кучи, а вообще любые $d$ -арные. Высота таких деревьев $\bigl\lfloor \log_d \bigl( n (d-1) \bigr) \bigr\rfloor + 1$ .

Точно так же, как и для двоичной кучи, у $d$ -арной кучи есть свойство кучи: значение любого узла больше значений всех его поддеревьев или, что то же самое, больше значений всех его детей.

Хранить полное $d$ -арное дерево можно точно так же в массиве. У элемента с индексом $i$ детьми являются элементы с индексами $di+1, d_i+2, \dotsc, di+d$ , а родителем — элемент с индексом $\lfloor (i-1) / d \rfloor$ .

Все операции: просеивание, вставка, извлечение максимума и построение выполняются точно так же, как и с обычной двоичной кучей.

Просеивание вверх требует максимум $\bigl\lfloor \log_d \bigl( n (d-1) \bigr) \bigr\rfloor$ обменов и сравнений, а просеивание вниз требует максимум $\bigl\lfloor \log_d \bigl( n (d-1) \bigr) \bigr\rfloor$ обменов и максимум $d \bigl\lfloor \log_d \bigl( n (d-1) \bigr) \bigr\rfloor$ сравнений.

Разберем операцию построения $d$ -арной кучи с помощью heapify. Количество сравнений для операции heapify равно

\sum\limits_{h=1}^{{\small\lfloor} \log_d {\small(} \mathstrut n (d-1) {\small)} {\small\rfloor} + 1} \Bigl\lceil \frac{n}{d^h} \Bigr\rceil \cdot (dh - d) = dn \sum\limits_{h=1}^{{\small\lfloor} \log_d {\small(} \mathstrut n (d-1) {\small)} {\small\rfloor} + 1} \frac{h-1}{d^h} = \frac{d^2}{(d-1)^2} \cdot n + O(\log_d n)

А количество обменов в $d$ раз меньше, $d / (d-1)^2 \cdot n + O(\log_d n)$ .

То есть операции выполняются за время

вставка — $O(\log_d n)$
извлечение максимума — $O(d \log_d n)$
построение $d$ -арной кучи — $O(n)$

При этом эффективность $d$ -арной кучи сильно растёт только при маленьких $d$ . Посмотрите на график зависимости числа сравнений $\log_d \bigr( n (d-1) \bigr)$ при вставке от размера кучи $n$ . Разными цветами обозначены графики для разных значений $d$ : от синего при $d=2$ до красного при $d=20$ .

Упражнения

Реализуйте бинарную кучу на массиве.

Необходимо реализовать поддержку следующих операций

heapify(array a) — создать кучу на массиве
insert(object x) — добавить объект x в кучу
change(int i, object x) — по заданному индексу i изменить значение элемента в куче на x
extract_min() — извлечь из кучи минимальный элемент
peek_min() — посмотреть, какой в куче минимальный элемент, не извлекая его

Напишите бенчмарки, которые замеряют время выполнения и количество операций сравнения для insert(object x), change(int i, object x) и extract_min() при разном размере кучи $n$ и при разных сценариях работы (много вставок, затем много извлечений; поочерёдные вставки и извлечения; случайные операции и так далее).

Постройте графики зависимости времени операции от $n$ и от $\log n$ .

Проведите аналогичные замеры для операции heapify(array a) и постройте график зависимости от $n$ при разных входных данных (почти отсортированный массив, обратно отсортированный, случайная перестановка и так далее).

Напишите код, который вычисляет точное количество куч, которые можно построить на массиве $\{1, 2, \dotsc, n\}$ . Постройте график зависимости логарифма количества куч от $n$ .