Куча против бинарного дерева поиска (BST)

170

В чем разница между кучей и BST?

Когда использовать кучу, а когда использовать BST?

Если вы хотите получить элементы в отсортированном виде, лучше ли BST по сравнению с кучей?

KC3
источник
13
Этот вопрос, кажется, не по теме, потому что он касается компьютерных наук и должен быть задан на cs.stackexchange.com
поток
3
@ Поток был задан там по адресу: cs.stackexchange.com/questions/27860/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Я чувствую, что это относится как к обмену стека, так и к переполнению стека. Так что иметь это здесь хорошо
Азизбро

Ответы:

191

Резюме

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Все средние значения времени в этой таблице совпадают с их худшими значениями времени, за исключением вставки.

  • *: везде в этом ответе BST == Сбалансированный BST, так как несбалансированный отстой асимптотически
  • **: используя тривиальную модификацию, объясненную в этом ответе
  • ***: log(n)для кучи дерева указателей, nдля кучи динамического массива

Преимущества двоичной кучи над BST

  • Среднее время вставки в двоичную кучу есть O(1), для BST есть O(log(n)). Это убийственная особенность куч.

    Существуют также другие кучи, которые достигают O(1)амортизированных (более сильных) значений , например, кучи Фибоначчи , и даже в худшем случае, например, очереди Бродала , хотя они могут быть непрактичными из-за неасимптотической производительности. Кучи Фибоначчи или очереди Бродала используются где-либо на практике?

  • двоичные кучи могут быть эффективно реализованы поверх динамических массивов или деревьев на основе указателей, BST только на деревьях на основе указателей. Таким образом, для кучи мы можем выбрать более компактную реализацию массива, если мы можем позволить себе время от времени изменять размер задержки.

  • создание двоичной кучи является O(n)худшим случаем , O(n log(n))для BST.

Преимущество BST над двоичной кучей

  • Поиск произвольных элементов есть O(log(n)). Это убийственная особенность BST.

    Для кучи это O(n)вообще, кроме самого большого элемента который есть O(1).

«Ложное» преимущество кучи перед BST

  • куча O(1)найти макс, BST O(log(n)).

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

    На самом деле, это ограничение кучи по сравнению с BST: единственный эффективный поиск - поиск самого большого элемента.

Средняя двоичная куча вставки O(1)

Источники:

Интуитивный аргумент:

  • нижние уровни дерева имеют экспоненциально больше элементов, чем верхние уровни, поэтому новые элементы почти наверняка будут идти внизу
  • вставка кучи начинается снизу , BST должна начинаться сверху

В двоичной куче увеличение значения по данному индексу также O(1)по той же причине. Но если вы хотите это сделать, вполне вероятно, что вы захотите поддерживать дополнительный индекс в актуальном состоянии для операций с кучей. Как реализовать операцию уменьшения ключа O (logn) для приоритетной очереди на основе минимальной кучи? например, для Дейкстры. Возможно без дополнительных затрат времени.

Тест вставки стандартной библиотеки GCC C ++ на реальном оборудовании

Я протестировал вставку C ++ std::set( красно-чёрное дерево BST ) и std::priority_queue( динамическая куча массивов ), чтобы убедиться, что я был прав насчет времени вставки, и вот что я получил:

введите описание изображения здесь

  • эталонный код
  • сюжетный сценарий
  • данные сюжета
  • протестировано на Ubuntu 19.04, GCC 8.3.0 на ноутбуке Lenovo ThinkPad P51 с процессором: процессор Intel Core i7-7820HQ (4 ядра / 8 потоков, база 2,90 ГГц, кэш 8 МБ), ОЗУ: 2x Samsung M471A2K43BB1-CRC (2x 16 ГБ) , 2400 Мбит / с), SSD: Samsung MZVLB512HAJQ-000L7 (512 ГБ, 3000 МБ / с)

Так ясно:

  • Время вставки кучи в основном постоянно.

    Мы ясно видим точки изменения размера динамического массива. Поскольку мы усредняем каждые 10 тыс. Вставок , чтобы увидеть что-либо выше системного шума , эти пики на самом деле примерно в 10 тыс. Раз больше, чем показано!

    Увеличенный график исключает по существу только точки изменения размера массива и показывает, что почти все вставки имеют размер менее 25 наносекунд.

  • BST является логарифмическим. Все вставки намного медленнее, чем вставка средней кучи.

  • Детальный анализ BST и hashmap: Какая структура данных находится внутри std :: map в C ++?

Стандарт вставки стандартной библиотеки GCC C ++ для gem5

gem5 - это симулятор полной системы, поэтому он обеспечивает бесконечно точные часы с помощью m5 dumpstats. Поэтому я попытался использовать его для оценки времени для отдельных вставок.

введите описание изображения здесь

Интерпретация:

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

    Это должно соответствовать задержкам при доступе к памяти для более высоких и более высоких вставок.

  • TODO Я не могу толковать BST полностью, так как он не выглядит таким логарифмическим и несколько более постоянным.

    Однако с помощью этой более подробной детализации мы также можем видеть несколько отдельных линий, но я не уверен, что они представляют: я ожидаю, что нижняя линия будет тоньше, так как мы вставляем верхнюю нижнюю часть?

Сравнительный анализ с этой установкой Buildroot на процессоре HPI aarch64 .

BST не может быть эффективно реализован в массиве

Операции с кучей должны только подниматься или опускаться на одну ветвь дерева, так что в O(log(n))худшем случае перестановки в O(1)среднем.

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

Кучи могут быть эффективно реализованы в массиве

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

Там нет операций балансировки, как BST.

Удалить мин - самая тревожная операция, так как она должна быть сверху вниз. Но это всегда можно сделать, «перколируя» одну ветвь кучи, как описано здесь . Это приводит к наихудшему случаю O (log (n)), поскольку куча всегда хорошо сбалансирована.

Если вы вставляете один узел для каждого удаляемого, то вы теряете преимущество асимптотической средней (1) вставки, которую обеспечивают кучки, так как удаление будет доминировать, и вы также можете использовать BST. Dijkstra, однако, обновляет узлы несколько раз для каждого удаления, поэтому мы в порядке.

Динамические массивы кучи против куч дерева указателей

Кучи могут быть эффективно реализованы поверх кучи указателей: возможно ли сделать эффективные реализации двоичной кучи на основе указателей?

Реализация динамического массива более экономична. Предположим, что каждый элемент кучи содержит только указатель на struct:

  • реализация дерева должна хранить три указателя для каждого элемента: parent, left child и right child. Таким образом, использование памяти всегда 4n(3 указателя дерева + 1 structуказатель).

    Древовидным BST также потребуется дополнительная информация о балансировке, например, черно-красная.

  • Реализация динамического массива может иметь размер 2nсразу после удвоения. Так в среднем так и будет 1.5n.

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

Тем не менее, дублирование массива резервных копий O(1)амортизируется, поэтому сводится к рассмотрению максимальной задержки. Упоминается здесь .

философия

  • BST поддерживают глобальное свойство между родителем и всеми потомками (слева меньше, справа больше).

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

    Это глобальное свойство более дорогое в обслуживании (log n insert), но дает более мощный поиск (log n search).

  • Кучи поддерживают локальное свойство между родительским и прямым потомками (parent> children).

    Верхний узел кучи - это большой элемент, который требует только локальных знаний (зная вашего родителя).

Сравнение BST против Heap и Hashmap:

  • BST: может быть либо разумным:

    • неупорядоченный набор (структура, которая определяет, был ли элемент ранее вставлен или нет). Но hashmap имеет тенденцию быть лучше из-за O (1) амортизированной вставки.
    • сортировочная машина. Но в этом случае куча, как правило, лучше, поэтому кучи гораздо более широко известны, чем сортировка по дереву.
  • куча: это просто сортировочная машина. Не может быть эффективным неупорядоченным набором, потому что вы можете быстро проверить только самый маленький / самый большой элемент.

  • карта хеша: может быть только неупорядоченным набором, а не эффективной сортировочной машиной, потому что хеширование смешивает любой порядок.

Двусвязный список

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

  • вставка:
    • позиция:
      • двусвязный список: вставленный элемент должен быть первым или последним, поскольку у нас есть только указатели на эти элементы.
      • двоичная куча: вставленный элемент может оказаться в любой позиции. Менее ограниченный, чем связанный список.
    • время:
      • двусвязный список: O(1)наихудший случай, поскольку у нас есть указатели на элементы, а обновление действительно простое
      • двоичная куча: O(1)средняя, ​​таким образом, хуже, чем связанный список. Компромисс для более общей позиции вставки.
  • поиск: O(n)для обоих

Вариант использования для этого - когда ключ кучи - текущая временная метка: в этом случае новые записи всегда будут идти в начало списка. Таким образом, мы можем вообще забыть точную метку времени и просто сохранить позицию в списке в качестве приоритета.

Это может быть использовано для реализации кэша LRU . Как и в случае с кучными приложениями, такими как Dijkstra , вам нужно сохранить дополнительную хэш-карту от ключа к соответствующему узлу списка, чтобы найти, какой узел быстро обновлять.

Сравнение разных сбалансированных BST

Хотя асимптотическое время вставки и поиска для всех структур данных, которые обычно классифицируются как «сбалансированные BST», которые я видел до сих пор, одинаково, разные BBST имеют разные компромиссы. Я еще не полностью изучил это, но было бы хорошо обобщить эти компромиссы здесь:

  • Красно-черное дерево . Похоже, что наиболее часто используемый BBST с 2019 года, например, это тот, который используется реализацией GCC 8.3.0 C ++
  • AVL дерево . Кажется, что он немного более сбалансирован, чем BST, поэтому он может быть лучше для латентности поиска за счет немного более дорогих находок. Вики резюмирует: «Деревья AVL часто сравнивают с красно-черными деревьями, потому что оба поддерживают один и тот же набор операций и требуют [одинакового] ​​времени для основных операций. Для приложений с интенсивным поиском деревья AVL быстрее, чем красно-черные деревья, потому что они более строго сбалансированы. Подобно красно-черным деревьям, деревья AVL сбалансированы по высоте. Оба, в общем, не сбалансированы ни по массе, ни по мю для любого мю <1/2, то есть узлы-братья могут иметь чрезвычайно различное количество потомков ".
  • WAVL . В оригинальной статье упоминаются преимущества этой версии с точки зрения ограничений на операции балансировки и вращения.

Смотрите также

Аналогичный вопрос по CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
источник
4
Я + 1, но «бумага», оправдывающая вставку средней двоичной кучи за O (1), теперь является мертвой ссылкой, а «слайды» просто заявляют утверждение без доказательства. Также я думаю, что это помогло бы уточнить, что «средний регистр» здесь означает среднее значение, предполагая, что вставленные значения получены из некоторого конкретного распределения , поэтому я не уверен, насколько «убийственной» эта функция на самом деле.
j_random_hacker
3
BST и сбалансированный BST, кажется, используются взаимозаменяемо. Должно быть ясно, что ответ относится к сбалансированному BST, чтобы избежать путаницы.
Гкалпак
2
@Bulat Я чувствую, что мы немного отвлеклись, но если мы хотим, чтобы и max, и min одновременно, мы могли бы столкнуться с проблемами с поддержанием двух куч, если мы не будем осторожны - stackoverflow.com/a/1098454/7154924 . Вероятно, лучше использовать кучу макс-мин (благодаря Аткинсону и др.), Которая специально разработана для этой цели.
flow2k
1
@CiroSantilli: Я не понимаю, почему операция удаления двоичной кучи - это O (log n). Это работает, только если у вас есть указатель на элемент в куче, но в большинстве случаев у вас есть ключ, и вам нужно сначала найти элемент, который принимает O (n).
Ricola
5
вставка кучи - лог (n), а не o (1)
Бобо
78

Heap просто гарантирует, что элементы на более высоких уровнях больше (для max-heap) или меньше (для min-heap), чем элементы на более низких уровнях, тогда как BST гарантирует порядок (от «левого» к «правому»). Если вы хотите отсортированные элементы, используйте BST.

Данте Мэй Код
источник
8
«Куча просто гарантирует, что элементы на более высоких уровнях больше (для max-heap) или меньше (для min-heap), чем элементы на более низких уровнях,…» - куча не применяет это на уровне , но только в parent-child- цепей. [1, 5, 9, 7, 15, 10, 11]представляет собой действительный мин-кучу, но 7на уровне 3 меньше , чем 9на уровне 2. Для визуализации, смотри , например , в 25и 19элементы в образце Википедии изображение для куч . (Также обратите внимание, что неравенство между элементами не является строгим, поскольку элементы не обязательно являются уникальными.)
Даниэль Андерссон
Извините за позднюю запись, но я просто хочу получить ясность. Если двоичная куча отсортирована, то наихудшим вариантом для поиска будет логарифм. Таким образом, в этом случае сортируются двоичные кучи лучше, чем деревья двоичного поиска (красно-черный BST). Спасибо
Кришна
50

Когда использовать кучу, а когда использовать BST

Куча лучше в findMin / findMax ( O(1)), в то время как BST хороша во всех find ( O(logN)). Вставка O(logN)для обеих структур. Если вы заботитесь только о findMin / findMax (например, о приоритете), используйте кучу. Если вы хотите, чтобы все отсортировано, используйте BST.

Первые несколько слайдов отсюда объясняют все очень четко.

xysun
источник
3
Хотя вставка является логарифмической для обоих в худшем случае, вставка средней кучи занимает постоянное время. (Так как большинство существующих элементов находятся внизу, в большинстве случаев новый элемент должен будет
всплыть
1
@xysun Я думаю, что BST лучше в findMin & findMax stackoverflow.com/a/27074221/764592
Yeo
2
@Yeo: куча лучше для findMin xor findMax. Если вам нужны оба , то лучше BST.
Mooing Duck
1
Я думаю, что это просто распространенное заблуждение. Бинарное дерево может быть легко изменено, чтобы найти минимальное и максимальное значения, как указано Yeo. На самом деле это ограничение кучи: единственная эффективная находка - это мин или макс. Истинное преимущество кучи O (1) средняя вставка , как я объясняю: stackoverflow.com/a/29548834/895245
Чиро Сантилли郝海东冠状病六四事件法轮功
1
Ответ Сиро Сантилли гораздо лучше: stackoverflow.com/a/29548834/2873507
Вик Седублью,
9

Как уже упоминалось, Heap может делать findMin или findMax в O (1), но не в обеих в одной и той же структуре данных. Однако я не согласен с тем, что Heap лучше в findMin / findMax. На самом деле, с небольшой модификацией, BST может делать как findMin и findMax в O (1).

В этом модифицированном BST вы отслеживаете узел min и узел max каждый раз, когда выполняете операцию, которая потенциально может изменить структуру данных. Например, в операции вставки вы можете проверить, больше ли минимальное значение, чем вновь вставленное значение, а затем назначить минимальное значение вновь добавленному узлу. Та же самая техника может быть применена к максимальному значению. Следовательно, этот BST содержит эту информацию, которую вы можете получить в O (1). (так же, как двоичная куча)

В этом BST (Сбалансированный BST), когда вы pop minили pop maxследующее минимальное значение, которое должно быть назначено, является преемником минимального узла, тогда как следующее максимальное значение, которое должно быть назначено, является предшественником максимального узла. Таким образом, он выполняет в O (1). Однако нам нужно перебалансировать дерево, поэтому оно все равно будет работать O (log n). (так же, как двоичная куча)

Мне было бы интересно услышать вашу мысль в комментарии ниже. Спасибо :)

Обновить

Перекрестная ссылка на аналогичный вопрос. Можем ли мы использовать двоичное дерево поиска для имитации операции с кучей? для дальнейшего обсуждения по моделированию кучи с использованием BST.

Ео
источник
Почему ты не согласен? Не могли бы вы поделиться своей мыслью ниже?
Yeo
Вы, конечно, можете хранить максимальное и / или минимальное значение BST, но что произойдет, если вы захотите добавить его? Вы должны найти дерево, чтобы удалить его, а затем снова искать новый максимум / мин, оба из которых являются O (log n) операциями. Это тот же порядок, что и для вставок и удалений в куче приоритетов, с худшей константой.
Джастин
@JustinLardinois Извините, я забыл выделить это в своем ответе. В BST, когда вы делаете pop min, следующее минимальное значение, которое должно быть назначено, является преемником минимального узла. и если вы установите максимальное значение, следующее максимальное значение, которое будет назначено, является предшественником максимального узла. Таким образом, он все еще выполняет в O (1).
Yeo
Исправление: for popMinили popMaxэто не O (1), но это O (log n), потому что это должен быть сбалансированный BST, который необходимо перебалансировать при каждой операции удаления. Следовательно, это то же самое, что двоичная куча popMinили popMaxкоторые запускаются O (log n)
Yeo
2
Вы можете получить первые min / max, но получение kth min / max вернулось бы к нормальной сложности BST.
Хаос
3

Бинарное дерево поиска использует определение: для каждого узла узел слева от него имеет меньшее значение (ключ), а узел справа от него имеет большее значение (ключ).

Где в качестве кучи, будучи реализацией двоичного дерева, использует следующее определение:

Если A и B являются узлами, где B является дочерним узлом A, тогда значение (ключ) A должно быть больше или равно значению (ключу) B. То есть ключ (A) ≥ ключ (B) ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

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

Евграф Андреевич Живаго
источник
«куча, являющаяся реализацией двоичного дерева» - просто указывает на то, что куча - это разновидность двоичного дерева, а не разновидность BST
Саад
3

Другое использование BST поверх Heap; из-за важной разницы:

  • Нахождение преемника и предшественника в BST займет O (h) времени. (O (logn) в сбалансированном BST)
  • находясь в куче, потребуется O (n) время, чтобы найти преемника или предшественника какого-либо элемента.

Использование BST поверх кучи : допустим, мы используем структуру данных для хранения времени посадки рейсов. Мы не можем запланировать полет на посадку, если разница во времени посадки меньше, чем «d». И предположим, что было запланировано много рейсов для посадки в структуре данных (BST или Heap).

Теперь мы хотим запланировать еще один рейс, который приземлится в t . Следовательно, нам нужно вычислить разницу t с ее преемником и предшественником (должно быть> d). Таким образом, для этого нам понадобится BST, который делает это быстро, т. Е. В O (logn), если сбалансирован.

Отредактированный:

Сортировка BST занимает O (n) время, чтобы напечатать элементы в отсортированном порядке (обход Inorder), в то время как Heap может сделать это за O (n logn) время. Куча извлекает элемент min и повторно накапливает массив, что заставляет его выполнять сортировку за O (n logn) времени.

CODError
источник
1
Да. Это от несортированной до отсортированной последовательности. O (n) время обхода по порядку BST, которое дает отсортированную последовательность. Находясь в кучах, вы извлекаете элемент min, а затем заново создаете кучу за O (log n) времени. Итак, для извлечения n элементов потребуется O (n logn). И это оставит вас с отсортированной последовательностью.
Ошибка кода
from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence.Ну, от несортированной последовательности до BST я не знаю метод, основанный на сравнении ключей с временем O (n logn), который доминирует от BST до части последовательности. (Принимая во внимание, что O (n) конструкция кучи.). Я бы посчитал справедливым (если не имеет смысла) утверждать, что кучи близки к несортировке, а BST отсортированы.
greybeard
Здесь я пытаюсь объяснить, что если у вас есть BST, а также куча из n элементов =>, то все элементы могут быть напечатаны в отсортированном порядке из обеих структур данных, а BST может сделать это за O (n) время (обход Inorder) ), в то время как куча заняла бы O (n logn) время. Я не понимаю, что вы пытаетесь сказать здесь. Как вы говорите, BST даст вам отсортированную последовательность в O (n logn).
Ошибка кода
Я думаю, что вы также рассматриваете время, необходимое для создания BST и кучи. Но я предполагаю, что у вас это уже есть, что вы создали его с течением времени, и теперь вы хотите получить отсортированный результат. Я не понимаю вашу точку зрения?
Ошибка кода
1
Отредактировано ... Я надеюсь, что вы удовлетворены сейчас; р и дать +1, если это правильно.
Ошибка кода
1

Вставка всех n элементов из массива в BST занимает O (n logn). n элементов в массиве могут быть вставлены в кучу за O (n) раз. Что дает кучу определенное преимущество

AMR
источник
0

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

Мне нравится приведенный выше ответ, и я оставляю свой комментарий более конкретным для моих потребностей и использования. Я должен был получить список n местоположений, найти расстояние от каждого местоположения до определенной точки, скажем (0,0), а затем вернуть местоположения, имеющие меньшее расстояние. Я использовал Приоритетную очередь, которая является кучей. Для нахождения расстояний и размещения в куче мне потребовалось n (log (n)) n-положений log (n) каждой вставки. Затем для получения m с наименьшими расстояниями потребовалось m (log (n)) m-положений log (n) удалений накопления.

Если бы мне пришлось сделать это с помощью BST, это заняло бы у меня n (n) вставку в худшем случае. (Скажем, первое значение очень меньше, а все остальные идут последовательно все длиннее и длиннее, а дерево охватывает только правого или левого потомка в случае все меньшего и меньшего. Мин потребовалось бы время O (1), но я снова должен был уравновесить. Таким образом, из моей ситуации и всех приведенных выше ответов я получаю, когда вы только после того, как значения на минимальной или максимальной приоритетной основе идут для кучи.

Сахиб Хан
источник