Пользователь
0,0
рейтинг
26 января 2011 в 19:10

Разработка → Структуры данных: двоичная куча (binary heap) из песочницы

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

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

Введение


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



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

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

public class BinaryHeap
{
    private List<int> list;

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

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


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



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





Иначе говоря, новый элемент «всплывает», «проталкивается» вверх, пока не займет свое место. Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна O(log2 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(log2 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 log2 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 log2 N). Следовательно, итоговая оценка O(N log2 N). При этом дополнительная память для массива не используется.

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

Заключение


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

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (55)

  • –5
    А я всегда думал что это называется дерево поиска, по крайней мере в университете нам так давали эту структуру данных и описана она в замечательной книге «Алгоритмы и структуры данных» Н. Вирта именно под этим названием.
    • +7
      Если бы я был тобой, я бы сначала сравнил двоичную кучу и дерево поиска хотя-бы с помощью википедии.
      • –2
        Ты прав, я не разобрался, синдром полуночного «хаброкомментера» )
    • 0
      они очень похоже. разница только в том, что (вики) «все слои, кроме, может быть, последнего, заполнены полностью, последний слой заполняется слева направо.» в остальном они одинаковы. для простого дерева поиска это не обязательно. для сбалансированного другие заморочки.
      • +2
        так, я ошибся. не бейте, пожалуйста.
  • +5
    Автор, ну расскажи в двух словах где применяется например.
    • 0
      heap sort на ней построен, если память не подводит…
      • 0
        Мда. Было про сортировку уже. Сорри.
      • 0
        Про heapSort, собственно, я в статье написал.
        • +1
          Имхо, следовало отметить, что хотя в heapSort гарантируется N log N (в отличие от qsort, где может быть и N^2), константный множитель больше, поэтому среднее время сортировки заметно превышает таковое для qsort.
        • 0
          Был бы еще он естественный — цены бы ему не было.
          А то так перетряхивает массив в процессе выполнения…
    • +1
      Например, там, где нужно быстро извлекать максимальный/минимальный элемент. Уже упомянутый алгоритм Дейкстры с хипом и, думаю, другие алгоритмы на графах. Еще, например, выбор m максимальных/минимальных элементов из массива.
    • +1
      Многопутевое слияние. Например, во внешних сортировках.
  • 0
    Хорошая статья, однако неплохо бы добавить примеров применения binary heap, дабы у читателя не возникло ощущения что он слушает лекцию про абстрактные материи. Сортировка это круто, но ведь двоичную кучу придумали не только для этого :)
    • 0
      Применяется, например, для ускорения алгоритма Дейкстры («узкое место» — нахождение самой близкой вершины). Правда, последний раз я её там писал, когда кодил на Delphi, а теперь использую красно-черные деревья — std::set, потому что они уже реализованы.
      • 0
        Спасибо, я знаю :)
        Мой комментарий был как раз про то, что неплохо бы увидеть эти примеры в статье.
      • 0
        priority_queue в С++ реализована с помощью бинарной кучи. И на практике алгоритм Дейкстры, использующий priority_queue оказывается немного быстрее варианта с set.

        А еще в STL также реализованы функции push_heap, pop_heap, make_heap и sort_heap.
        • 0
          На олимпиадах ни разу не подвело. Однако там ограничения обычно совсем не впритык.
        • 0
          priority_queue в свою очередь полезно, например, для эффективной реализации алгоритма Форда-Фалкерсона поиска максимального потока в сети. А он уже для много чего полезен :-)
      • НЛО прилетело и опубликовало эту надпись здесь
    • НЛО прилетело и опубликовало эту надпись здесь
  • +3
    Пост не полон без доказательства того, что построение действительно O(n). Ну, или хотя бы упоминания о тонкостях.
    • –1
      Хотя, впрочем, чего я докапываюсь. Отличный повод вспомнить первый курс, спасибо за статью.
    • +1
      O(n) требуется, чтобы построить дерево, не обращая внимание на соблюдение основного свойства кучи. Чтобы упорядочить binaryHeap, log2N раз вызываем метод heapify, сложность которого O(log2N), то есть процесс упорядочения более быстр. Поэтому итоговая оценка O(n).
      • 0
        Точнее, метод heapify вызывается (log2N)/2 раз, что, впрочем, ничего не меняет.
      • 0
        Он же вызывается O(n) раз, нет?
        public void buildHeap(int[] sourceArray)
        {
            list = sourceArray.ToList();
            for (int i = /* !!! */ heapSize / 2; i >= 0; i--)
            {
                heapify(i);
            }
        }
        
        • 0
          OH SHI~
          Вы правы, я ошибся.
          • 0
            То есть всё-таки построение отъедает N log N? Тогда поправьте статью :-)
            • +2
              Нет, нет отъедает:) Итак:

              Метод heapify вызывается только для поддеревьев, состоящих более чем из одного элемента. То есть для деревьев высоты 2, 3,…, H (пусть H=log2N — высота дерева), причем поддеревьев высоты k всего есть 2H-k.

              heapify «жрет» не более O(log2N), а на самом деле O(h), где h — высота поддерева, для которого heapify вызывается. Тогда итоговая сложность упорядочения будет равна (k пробегает по всем значениям высот поддеревьев, которые нас интересуют)

              причем 2H — это количество вершин в дереве, то есть N. А сумма

              не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)
              • 0
                *алгоритма
              • 0
                Ок, достаточно убедительно :-)
  • 0
    Несколько вопросов. Как насчет удаления узла из кучи? Чем двоичная куча лучше/хуже дерева поиска? Может есть какие-то конкретные задачи, которые лучше решаются той или иной структурой? И главный вопрос, что такого есть в статье, чего нет в вики на эту же тему?
    • 0
      Ох, просмотрел про удаление, каюсь.
  • –2
    Мда. Не думал, что на хабре будут выкладывать стандартные алгоритмы/стрруктуры, которые можно найти в большенстве учебников/справочников. Могу сразу посоветовать «Корман. Алгоритмы и структуры данных. 2е издание», «Кнут. Все 3 тома» и сайт e-maxx.ru с описаниями и кодами большенства (а то чуть ли не всех) частоиспользуемых алгоритмов.
    • 0
      Не думал, что на хабре будут выкладывать стандартные алгоритмы/стрруктуры, которые можно найти в большенстве учебников/справочников.

      Например вот эти статьи вам тоже не нравятся? А структуры данных описанные в них спокойно можно найти в Кормене/Кнуте или на емаксе.
      «Фуууу, хабр уже не торт, расходимся пацаны !»
      • +4
        Только недавно кто-то оставлял комментарий, не смог найти автора:
        Действительно. Что делает техническая статья на развлекательном и новостном ресурсе?
      • 0
        Извиняюсь, проглядел я их) Да, тоже не нравятся. Хотя согласен с тем, что декартово дерево не сильно тривиально для понимания и в нём много особенностей, так что с его описанием я не спорю.
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Какой-то слабый аргумент. Чтобы прочитать эту статью и осознать, тоже нужен определенный уровень подготовки. В частности представление о деревьях и оценке сложности алгоритмов (как написано в введении к статье). А это уже вполне сносный уровень, чтобы читать Кормана и Ко. Ну а если есть хоть какое-то образование выше среднего, то думаю любому по силам.

        Статья откровенно ни о чем, ибо обычный пересказ вики с небольшими примерами на С#. Максимум кому это интересно, это тем новичкам в шарпе, кто не в состоянии реализовать данную структуру. Но для этого есть гугл и мозги.
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Ну что ж, жаль, что не откроют. Клёвые книжки ;) Использовать данные книги как справочники, мне кажется, вполне логично, если не занимаешься непосредственно разработкой различных алгоритмов. Сложно придумать новый алгоритм, не зная основ.
            • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Потомки гарантированно есть у первых heapSize/2 вершин.
    for (int i = heapSize / 2; i >= 0; i--)

    Мне кажется, или нужно сдвинуть верхнюю границу цикла?

    for (int i = heapSize / 2 — 1; i >= 0; i--)

    Дерево на первом рисунке имеет 10 вершин, т.о. потомки есть у первых пяти вершин, но индексы-то с нуля идут.
    • 0
      И еще вопрос в дополнение к тому же алгоритму. Поскольку на вход подается неупорядоченный массив, где гарантия, что «поднятию» подвергнутся вершины, имеющие потомков?
      • 0
        Простите, не вполне понял суть вопроса. Тем не менее, гарантия того, что обрабатываются вершины, имеющие потомков, — сама структура дерева. К тому же они не «поднимаются», а «опускаются».
        • 0
          Этот вопрос я снимаю. Неверно его сформулировал, сейчас разобрался.
  • +1
    Для интересующихся визуализатор:
    rain.ifmo.ru/cat/view.php/vis/heaps/bls-2006
  • +5
    • –1
      Чорт, реально дерево и куча=)
  • 0
    Вероятно, я слегка запоздал с комментарием, но всё же )
    ====
    Наиболее очевидный способ построить binary heap из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма O(N log2 N).
    ====
    Далее говорится о том, что при построении кучи методом обхода с конца массива (точнее, примерно с середины, по сути) сложность будет линейной. Вопрос. Чем эти 2 случая принципиально отличаются? При обходе с начала мы имеем те же N уровней высоты/глубины, но «просеивание» выполняем вверх, а не вниз, как при обходе с конца. Оба варианта «просеивания» имеют логарифмическую сложность. Кто-то может объяснить, в чем тут подвох? )
    • 0
      Я уже отвечал на подобный вопрос.
      • 0
        Я очень внимательно прочитал Ваш комментарий вверху и согласен с тем, что для «обратного» прохода по неупорядоченному массиве можно построить кучу за O(n).
        Но почему этого нельзя сделать для варианта «прямого» прохода по массиву? Ведь тут работает та же формула. Для каждого уровня глубины h от 0 до log2(n) мы выполняем для
        того же количества узлов на каждом уровне глубины операцию «просеивания» вверх, которая в худшем случае выполняется за h обменов.
        • 0
          Если добавлять каждую вершину в конец дерева, ее придется проталкивать вверх, а не вниз. Это невыгодно, так как сложность проталкивания вверх пропорциональна высоте уже построенного дерева, а вниз — высоте поддерева.
          Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
          Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.
          • 0
            Кажется, я сообразил. При построении кучи методом «обратного» обхода массива у нас будет в худшем случае (для изображенного Вами варианта дерева): 4 * 1 замены для узлов глубины 2, 2 * 2 замены для узлов глубины 1 и 3 замены для корня. Итого 11. При этом мы полностью пропускаем узлы, не имеющие детей.
            При использовании метода «прямого» обхода массива в худшем случае у нас будет 2 замены для узлов уровня глубины 1, 4 * 2 замены для узлов уровня глубины 2 и 8 * 3 замен для узлом самого нижнего уровня глубины — третьего. Итого 34.
            Таким образом, вариант добавления узлов в начало дерево (с обходом с конца массива) более экономичен. Я правильно понял?
            • 0
              В общем-то да.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.