awolf26 янв 2011 в 16:10

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

4 мин

275K

Алгоритмы *

Из песочницы

+44

Комментарии 59

Ilya_Smelykh 26 янв 2011 в 16:56

А я всегда думал что это называется дерево поиска, по крайней мере в университете нам так давали эту структуру данных и описана она в замечательной книге «Алгоритмы и структуры данных» Н. Вирта именно под этим названием.

Flux 26 янв 2011 в 17:03

Если бы я был тобой, я бы сначала сравнил двоичную кучу и дерево поиска хотя-бы с помощью википедии.

Ilya_Smelykh 26 янв 2011 в 18:07

Ты прав, я не разобрался, синдром полуночного «хаброкомментера» )

Jabberwok 26 янв 2011 в 17:15

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

Jabberwok 26 янв 2011 в 17:17

так, я ошибся. не бейте, пожалуйста.

blaze79 22 мая 2019 в 11:12

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

Jabberwok 22 мая 2019 в 15:13

да да, все так. Удивлен что кто-то заметил мой комментарий спустя 8 лет…

blaze79 22 мая 2019 в 17:43

внезпано гугл выдает в топе

AlexanderYastrebov 26 янв 2011 в 17:33

Автор, ну расскажи в двух словах где применяется например.

denlion 26 янв 2011 в 18:30

heap sort на ней построен, если память не подводит…

denlion 26 янв 2011 в 18:32

Мда. Было про сортировку уже. Сорри.

awolf 26 янв 2011 в 18:32

Про heapSort, собственно, я в статье написал.

tagir_valeev 26 янв 2011 в 19:19

Имхо, следовало отметить, что хотя в heapSort гарантируется N log N (в отличие от qsort, где может быть и N^2), константный множитель больше, поэтому среднее время сортировки заметно превышает таковое для qsort.

Nostr 30 янв 2011 в 06:01

Был бы еще он естественный — цены бы ему не было.
А то так перетряхивает массив в процессе выполнения…

awolf 26 янв 2011 в 18:35

Например, там, где нужно быстро извлекать максимальный/минимальный элемент. Уже упомянутый алгоритм Дейкстры с хипом и, думаю, другие алгоритмы на графах. Еще, например, выбор m максимальных/минимальных элементов из массива.

Sonic_SE 27 янв 2011 в 06:33

Многопутевое слияние. Например, во внешних сортировках.

Flux 26 янв 2011 в 17:34

Хорошая статья, однако неплохо бы добавить примеров применения binary heap, дабы у читателя не возникло ощущения что он слушает лекцию про абстрактные материи. Сортировка это круто, но ведь двоичную кучу придумали не только для этого :)

yeputons 26 янв 2011 в 17:41

Применяется, например, для ускорения алгоритма Дейкстры («узкое место» — нахождение самой близкой вершины). Правда, последний раз я её там писал, когда кодил на Delphi, а теперь использую красно-черные деревья — std::set, потому что они уже реализованы.

Flux 26 янв 2011 в 17:46

Спасибо, я знаю :)
Мой комментарий был как раз про то, что неплохо бы увидеть эти примеры в статье.

KapJI 26 янв 2011 в 18:44

priority_queue в С++ реализована с помощью бинарной кучи. И на практике алгоритм Дейкстры, использующий priority_queue оказывается немного быстрее варианта с set.

А еще в STL также реализованы функции push_heap, pop_heap, make_heap и sort_heap.

yeputons 26 янв 2011 в 18:48

На олимпиадах ни разу не подвело. Однако там ограничения обычно совсем не впритык.

tagir_valeev 26 янв 2011 в 19:20

priority_queue в свою очередь полезно, например, для эффективной реализации алгоритма Форда-Фалкерсона поиска максимального потока в сети. А он уже для много чего полезен :-)

НЛО прилетело и опубликовало эту надпись здесь

aabzel 14 авг в 15:15

Хорошая статья, однако неплохо бы добавить примеров применения binary heap, дабы у читателя не возникло ощущения что он слушает лекцию про абстрактные материи

Можно в очереди к врачу стоять в виде бинарной кучи.

FLashM 26 янв 2011 в 17:43

Пост не полон без доказательства того, что построение действительно O(n). Ну, или хотя бы упоминания о тонкостях.

FLashM 26 янв 2011 в 17:49

Хотя, впрочем, чего я докапываюсь. Отличный повод вспомнить первый курс, спасибо за статью.

awolf 26 янв 2011 в 18:40

O(n) требуется, чтобы построить дерево, не обращая внимание на соблюдение основного свойства кучи. Чтобы упорядочить binaryHeap, log₂N раз вызываем метод heapify, сложность которого O(log₂N), то есть процесс упорядочения более быстр. Поэтому итоговая оценка O(n).

awolf 26 янв 2011 в 18:43

Точнее, метод heapify вызывается (log₂N)/2 раз, что, впрочем, ничего не меняет.

yeputons 26 янв 2011 в 18:50

Он же вызывается O(n) раз, нет?

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

awolf 26 янв 2011 в 19:00

OH SHI~
Вы правы, я ошибся.

tagir_valeev 26 янв 2011 в 19:21

То есть всё-таки построение отъедает N log N? Тогда поправьте статью :-)

awolf 26 янв 2011 в 20:03

Нет, нет отъедает:) Итак:

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

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

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

не превосходит некоторой константы (хотите доказательство?). Значит, общее время работы алгоритмы все-таки O(N) :)

awolf 26 янв 2011 в 20:03

*алгоритма

tagir_valeev 26 янв 2011 в 20:08

Ок, достаточно убедительно :-)

НЛО прилетело и опубликовало эту надпись здесь

DeMoN_MIPT 26 янв 2011 в 21:28

Мда. Не думал, что на хабре будут выкладывать стандартные алгоритмы/стрруктуры, которые можно найти в большенстве учебников/справочников. Могу сразу посоветовать «Корман. Алгоритмы и структуры данных. 2е издание», «Кнут. Все 3 тома» и сайт e-maxx.ru с описаниями и кодами большенства (а то чуть ли не всех) частоиспользуемых алгоритмов.

Flux 26 янв 2011 в 22:12

Не думал, что на хабре будут выкладывать стандартные алгоритмы/стрруктуры, которые можно найти в большенстве учебников/справочников.

Например вот эти статьи вам тоже не нравятся? А структуры данных описанные в них спокойно можно найти в Кормене/Кнуте или на емаксе.
«Фуууу, хабр уже не торт, расходимся пацаны !»

TheShock 26 янв 2011 в 22:15

Только недавно кто-то оставлял комментарий, не смог найти автора:

Действительно. Что делает техническая статья на развлекательном и новостном ресурсе?

DeMoN_MIPT 26 янв 2011 в 22:20

Извиняюсь, проглядел я их) Да, тоже не нравятся. Хотя согласен с тем, что декартово дерево не сильно тривиально для понимания и в нём много особенностей, так что с его описанием я не спорю.

НЛО прилетело и опубликовало эту надпись здесь

andreycha 26 янв 2011 в 22:38

Потомки гарантированно есть у первых heapSize/2 вершин.
for (int i = heapSize / 2; i >= 0; i--)

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

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

Дерево на первом рисунке имеет 10 вершин, т.о. потомки есть у первых пяти вершин, но индексы-то с нуля идут.

andreycha 26 янв 2011 в 23:00

И еще вопрос в дополнение к тому же алгоритму. Поскольку на вход подается неупорядоченный массив, где гарантия, что «поднятию» подвергнутся вершины, имеющие потомков?

awolf 27 янв 2011 в 14:32

Простите, не вполне понял суть вопроса. Тем не менее, гарантия того, что обрабатываются вершины, имеющие потомков, — сама структура дерева. К тому же они не «поднимаются», а «опускаются».

andreycha 27 янв 2011 в 15:33

Этот вопрос я снимаю. Неверно его сформулировал, сейчас разобрался.

Joshik 26 янв 2011 в 22:55

Для интересующихся визуализатор:
rain.ifmo.ru/cat/view.php/vis/heaps/bls-2006

Teivaz 27 янв 2011 в 09:42

burdakovd 27 янв 2011 в 09:59

Чорт, реально дерево и куча=)

tvolf 10 сен 2011 в 12:12

Вероятно, я слегка запоздал с комментарием, но всё же )
====
Наиболее очевидный способ построить binary heap из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма O(N log2 N).
====
Далее говорится о том, что при построении кучи методом обхода с конца массива (точнее, примерно с середины, по сути) сложность будет линейной. Вопрос. Чем эти 2 случая принципиально отличаются? При обходе с начала мы имеем те же N уровней высоты/глубины, но «просеивание» выполняем вверх, а не вниз, как при обходе с конца. Оба варианта «просеивания» имеют логарифмическую сложность. Кто-то может объяснить, в чем тут подвох? )

awolf 10 сен 2011 в 12:50

Я уже отвечал на подобный вопрос.

tvolf 10 сен 2011 в 14:10

Я очень внимательно прочитал Ваш комментарий вверху и согласен с тем, что для «обратного» прохода по неупорядоченному массиве можно построить кучу за O(n).
Но почему этого нельзя сделать для варианта «прямого» прохода по массиву? Ведь тут работает та же формула. Для каждого уровня глубины h от 0 до log2(n) мы выполняем для
того же количества узлов на каждом уровне глубины операцию «просеивания» вверх, которая в худшем случае выполняется за h обменов.

awolf 10 сен 2011 в 15:35

Если добавлять каждую вершину в конец дерева, ее придется проталкивать вверх, а не вниз. Это невыгодно, так как сложность проталкивания вверх пропорциональна высоте уже построенного дерева, а вниз — высоте поддерева.
Пример на пальцах: если в дереве 15 вершин и используется оптимальный метод, то есть только одна вершина, которую (возможно) придется протолкнуть вниз на 3 уровня. На рисунке красная.
Если же добавлять вершины по одной, то есть 8 вершин, которые (возможно) придется проталкивать вверх на 3 уровня. Это зеленые вершины.

tvolf 10 сен 2011 в 16:51

Кажется, я сообразил. При построении кучи методом «обратного» обхода массива у нас будет в худшем случае (для изображенного Вами варианта дерева): 4 * 1 замены для узлов глубины 2, 2 * 2 замены для узлов глубины 1 и 3 замены для корня. Итого 11. При этом мы полностью пропускаем узлы, не имеющие детей.
При использовании метода «прямого» обхода массива в худшем случае у нас будет 2 замены для узлов уровня глубины 1, 4 * 2 замены для узлов уровня глубины 2 и 8 * 3 замен для узлом самого нижнего уровня глубины — третьего. Итого 34.
Таким образом, вариант добавления узлов в начало дерево (с обходом с конца массива) более экономичен. Я правильно понял?

awolf 10 сен 2011 в 16:58

В общем-то да.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий