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

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

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

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

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

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

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

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

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

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

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;
    }
}

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

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

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

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;
    }
}

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

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

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

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

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

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

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

Приложение к лекции.

using System;
using System.Collections.Generic;
using System.Net.Sockets;
using System.Runtime.InteropServices;

namespace ConsoleApplication46
{
    internal class Program
    {
        private static List<int> _list;

        public static void Main(string[] args)
        {
            _list = new List<int>();
            add(5);
            add(7);
            add(9);
            add(11);
            add(3);
            add(7);
            add(15);
            Print();
            int x = GetMax();
            Console.WriteLine(x);
            Print();
        }

        private static 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;
            }
        }

        private static 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;
            }
        }

        private static int GetMax()
        {
            int result = _list[0];
            _list[0] = _list[HeapSize() - 1];
            _list.RemoveAt(HeapSize() - 1);
            Heapify(0);
            return result;
        }

        private static int HeapSize()
        {
            return _list.Count;
        }

        private static void Print()
        {
            int i = 0;
            int k = 1;
            while (i < HeapSize())
            {
                while ((i < k) && (i < HeapSize()))
                {
                    Console.Write(_list[i] + " ");
                    i++;
                }

                Console.WriteLine();
                k = k * 2 + 1;
            }
        }
    }
}

Итоги занятия.