Структуры данных: двоичная куча (binary heap)

Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).

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

Введение

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap, поскольку корень поддерева является максимумом из значений элементов поддерева. В этой статье для простоты используется именно такое представление. Напомню также, что дерево называется полным бинарным, если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).



Двоичную кучу удобно хранить в виде одномерного массива, причем левый потомок вершины с индексом i имеет индекс 2*i+1, а правый 2*i+2. Корень дерева – элемент с индексом 0. Высота двоичной кучи равна высоте дерева, то есть log₂ N, где N – количество элементов массива.

Приведу заготовку класса на C#:

public class BinaryHeap
{
    private List<int> list;

    public int heapSize
    {
        get
        {
            return this.list.Count();
        }
    }
}

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

Новый элемент добавляется на последнее место в массиве, то есть позицию с индексом heapSize:



Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае следует «поднимать» новый элемент на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи:





Иначе говоря, новый элемент «всплывает», «проталкивается» вверх, пока не займет свое место. Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна O(log₂ N).

public void add(int value)
{
    list.Add(value);
    int i = heapSize - 1;
    int parent = (i - 1) / 2;

    while (i > 0 && list[parent] < list[i])
    {
        int temp = list[i];
        list[i] = list[parent];
        list[parent] = temp;

        i = parent;
        parent = (i - 1) / 2;
    }
}

Упорядочение двоичной кучи

В ходе других операций с уже построенной двоичной кучей также может нарушиться основное свойство кучи: вершина может стать меньше своего потомка.



Метод heapify восстанавливает основное свойство кучи для дерева с корнем в i-ой вершине при условии, что оба поддерева ему удовлетворяют. Для этого необходимо «опускать» i-ую вершину (менять местами с наибольшим из потомков), пока основное свойство не будет восстановлено (процесс завершится, когда не найдется потомка, большего своего родителя). Нетрудно понять, что сложность этого алгоритма также равна O(log₂ N).

public void heapify(int i)
{
    int leftChild;
    int rightChild;
    int largestChild;

    for (; ; )
    {
        leftChild = 2 * i + 1;
        rightChild = 2 * i + 2;
        largestChild = i;

        if (leftChild < heapSize && list[leftChild] > list[largestChild]) 
        {
            largestChild = leftChild;
        }

        if (rightChild < heapSize && list[rightChild] > list[largestChild])
        {
            largestChild = rightChild;
        }

        if (largestChild == i) 
        {
            break;
        }

        int temp = list[i];
        list[i] = list[largestChild];
        list[largestChild] = temp;
        i = largestChild;
    }
}

Построение двоичной кучи

Наиболее очевидный способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма O(N log₂ N). Однако можно построить кучу еще быстрее — за О(N). Сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод heapify для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). Потомки гарантированно есть у первых heapSize/2 вершин.

public void buildHeap(int[] sourceArray)
{
    list = sourceArray.ToList();
    for (int i = heapSize / 2; i >= 0; i--)
    {
        heapify(i);
    }
}

Извлечение (удаление) максимального элемента

В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав heapify для корня, то есть упорядочив все дерево.

public int getMax()
{
    int result = list[0];
    list[0] = list[heapSize - 1];
    list.RemoveAt(heapSize - 1);
    return result;
}

Сортировка с применением двоичной кучи

Заметим, что можно отсортировать массив, сначала построив из него двоичную кучу, а потом последовательно извлекая максимальные элементы. Оценим временную сложность такого элемента: построение кучи – O(N), извлечение N элементов – O(N log₂ N). Следовательно, итоговая оценка O(N log₂ N). При этом дополнительная память для массива не используется.

public void heapSort(int[] array)
{
    buildHeap(array);
    for (int i = array.Length - 1; i >= 0; i--)
    {
        array[i] = getMax();
        heapify(0);
    }
}

Заключение

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