Двоичные кучи. Очередь с приоритетами

Двоичная куча (пирамида, сортирующее дерево, binary heap) это полное двоичное дерево, где поддерживается свойство порядка размещения вершин (heap order property).

Напомним, что полное двоичное дерево (complete binary tree) это такое дерево, все уровни которого заполнены, возможно, за исключением последнего:

Свойство порядка размещения вершин (heap order property) заключается в том, что двоичная куча может быть максимальной (maximum heap) или минимальной (minimum heap):

• maximum heap - если значение (приоритет) в каждом узле больше или равно значениям в узлах потомков;
• minimum heap - если значение (приоритет) в каждом узле меньше или равно значениям в узлах потомков.

Двоичную кучу легко представить в виде массива¹:

Вершиной такого дерева является элемент с индексом 0. Для i-го узла достаточно просто вычислить его родителя и его потомков:

int parent(int i)
{
    return (i-1) / 2;
}

int left(int i)
{
    return 2*i + 1;
}

int right(int i)
{
    return 2*i + 2;
}

Предположим, что у нас есть куча со свойством maximum heap, тогда операции добавления или удаления элементов из кучи могут нарушить это свойство (аналогично и для кучи со свойством minimum heap). Восстановить это свойство позволит функция heapify:

bool max_heap(EType a, Etype b) { return a > b ? true : false; }
bool min_heap(EType a, Etype b) { return a < b ? true : false; }

void heapify(Array A, int heap_size, int i, bool (*cmp)(EType, EType))
{
    int l = left(i);
    int r = right(i);
    int current = i;

    if (l < heap_size && cmp(get(A, l), get(A, current)))
        current = l;
    if (r < heap_size && cmp(get(A, r), get(A, current)))
        current = r;

    if (current != i)
    {
        swap(A, i, current);
        heapify(A, heap_size, current, cmp);
    }
}

Если i-й элемент больше (меньше), чем его сыновья, то всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами i-й элемент с наибольшим (наименьшим) из его сыновей, после чего выполняем heapify для этого сына.

Для построения кучи из неупорядоченного массива элементов достаточно последовательно применить heapify ко всем элементам кучи, у которых есть сыновья:

void build_heap(Array A, bool(*cmp)(EType, EType))
{
    for (int i = size(A)/2 - 1; i >= 0; i--)
       heapify(A, size(A), i, cmp);
}

Иллюстрация работы функции build_heap:

Над кучами также можно выполнять следующие операции:

• heap_insert(H, e, cmp) - вставка элемента e в кучу H;
• heap_get(H) - получить значение максимального/минимального элемента (без его удаления) в куче H;
• heap_extract(H) - удалить максимальный/минимальный элемент из кучи H;
• heap_union(H1, H2, cmp) - объединить кучи H1 и H2.

Алгоритм вставки элемента достаточно простой, мы добавляем новый элемент в конец массива и затем двигаем его вверх по дереву до тех пор, пока значение в родителе не станет больше/меньше чем значение, которое мы добавляем:

void heap_insert(Array A, EType k, bool (*cmp)(EType, EType))
{
    add(A, k);
    heap_shift_up(A, size(A)-1, cmp);
}

void heap_shift_up(Array A, int i, bool (*cmp)(EType, EType))
{
    while (i > 0 && cmp(get(A, i), get(A, parent(i))))
    {
        swap(A, i, parent(i));
        i = parent(i);
    }
}

Для того, чтобы получить значение максимального или минимального элемента (в зависимости от поддерживаемого свойства) достаточно обратиться к нулевому элементу массива:

EType heap_get(Array A)
{
    return get(A, 0);
}

Удаление элемента производится путем замены значения, которое находилось в вершине, на значение последнего узла в дереве с последующим удалением этого узла. После замены выполняется функция heapify над новой вершиной:

EType heap_extract(Array A, bool (*cmp)(EType, EType))
{
    if (size (A) <= 0)
    {
        fprintf(stderr, "Heap underflow");
        exit(1);
    }
    EType e = heap_get(A);
    set(A, 0, get(A, size(A) - 1));
    remove(A);
    heapify(A, size(A), 0, cmp);
    return e;
}

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

Кучи часто используются в двух случаях:

• для сортировки массива;
• для реализации очереди с приоритетами.

Сортировка массива с использованием кучи называется пирамидальной сортировкой (сортировка кучей, heapsort). Эта сортировка является улучшенной версией сортировки выбором, которая работает за время $O(n^2)$ по следующему алгоритму:

Пока размер неотсортированной части > 1:
    Найти максимальный элемент
    Переставить его в конец отсортированной части
Конец

Так как перестановка элемента выполняется за $O(1)$, то улучшить мы можем только поиск максимального (минимального) элемента. Для этого нам нужно извлечь из кучи максимальный элемент и выполнить функцию heapify(), которая работает за $O(log(n))$, чтобы восстановить свойство кучи. Таким образом, сортировка кучей имеет следующий алгоритм и работает за $O(n)\times O(log(n)) = O(nlog(n))$:

Преобразовать массив в кучу
Пока размер кучи > 1:
    Выбрать максимальный элемент
    Перенести его в отсортированную часть
Конец

void heap_sort(Array A, int(*cmp)(EType, EType))
{
    for (int i = size(A) - 1; i > 0; i--)
    {
        swap(A, 0, i);
        heapify(A, i, 0, cmp);
    }
}

Иллюстрация работы функции heap_sort:

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

Как было отмечено ранее, еще одним применением двоичных куч является очередь с приоритетами. Очередь с приоритетами (priority queue) это структура данных, представляющая собой обычную очередь, элементы которой упорядочены по их приоритету.

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

Очередь с приоритетами может работать как по вставке, так и по извлечению. Если очередь работает по вставке, то при добавлении нового элемента мы ищем в очереди позицию, в которую будет произведена вставка. Если очередь работает по вставке, то при извлечении элемента из очереди, мы ищем позицию, с которой элемент должен быть удален².

Операции над очередью с приоритетами:

• pq_insert(PQ, e) - добавить в очередь PQ элемент e;
• pq_delete(PQ) - удаляет из очереди PQ элемент с наивысшим приоритетом;
• pq_peek(PQ) - возвращает иp очереди PQ элемент с наивысшим приоритетом (без удаления);
• pq_size(PQ) - возвращает количество элементов в очереди PQ;
• pq_is_empty(PQ) - проверить является ли очередь PQ пустой.

size_t pq_size(Array PQ)
{
    return size(PQ);
}

bool is_empty(Array PQ)
{
    return pq_size(PQ) == 0;
}

¹ Наша реализация кучи основана на реализации динамических массивов.

² Очевидно, что очередь по вставке работает быстрее.

Задания

Задание 1: Напишите функцию heap_union(H1, H2), которая объединяет две кучи.

Задание 2: Напишите функцию is_complete(H), которая проверяет является ли куча H полным бинарным деревом.

Задание 3: Напишите функцию has_value_property(H, cmp), которая проверяет обладает ли куча H свойством cmp.