В чем разница между двоичным деревом поиска и двоичной кучей?

Эти два кажутся очень похожими и имеют почти идентичную структуру. Какая разница? Каковы временные сложности для разных операций каждого?

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

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

от xysun

Как двоичные деревья поиска, так и двоичные кучи являются структурами данных на основе дерева.

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

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

BST имеют среднее значение для вставки, удаления и поиска. Двоичные кучи имеют среднее значение для findMin / findMax и для вставки и удаления.$O(\log n)$
$O(1)$$O(\log n)$

Резюме

          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)амортизированных (более сильных), например, кучи Фибоначчи , и даже в худшем случае, например, очереди Бродала , хотя они могут быть непрактичными из-за неасимптотической производительности: https://stackoverflow.com/questions/30782636 / ARE-Фибоначчи куча или-Бродал-очередь используемая в практике- в любом месте

• двоичные кучи могут быть эффективно реализованы поверх динамических массивов или деревьев на основе указателей, 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 для отслеживания самого большого элемента и обновлять его всякий раз, когда этот элемент может быть изменен: при вставке большего свопа, при удалении найдите второе по величине. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (упомянуто Yeo ).

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

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

Источники:

• Документ: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Слайды WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

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

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

В двоичной куче увеличение значения по данному индексу также O(1)по той же причине. Но если вы хотите это сделать, вполне вероятно, что вы захотите поддерживать дополнительный индекс в актуальном состоянии для операций с кучей https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- key-operation-for-min-heap-based-priority-queu например для Дейкстры. Возможно без дополнительных затрат времени.

Стандарт вставки стандартной библиотеки 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 против хэш-карты по адресу: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

Стандарт вставки стандартной библиотеки 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, однако, обновляет узлы несколько раз для каждого удаления, так что мы в порядке.

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

Кучи могут быть эффективно реализованы поверх кучи указателей: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Реализация динамического массива более экономична. Предположим, что каждый элемент кучи содержит только указатель на 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).

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

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

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

• вставка:
  • позиция:
    • двусвязный список: вставленный элемент должен быть первым или последним, поскольку у нас есть только указатели на эти элементы.
    • двоичная куча: вставленный элемент может оказаться в любой позиции. Менее ограниченный, чем связанный список.
  • время:
    • двусвязный список: 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: В чем разница между бинарным деревом поиска и бинарной кучей?

Со структурой данных нужно различать уровни беспокойства.

1. Эти абстрактные структуры данных (объекты , хранящиеся, их операция) в этом вопросе различны. Один реализует приоритетную очередь, другой - набор. Очередь с приоритетом не заинтересована в поиске произвольного элемента, только тот, который имеет наибольший приоритет.

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

3. Существует заключительная разница в реализации низкого уровня . (Несбалансированное) двоичное дерево поиска имеет стандартную реализацию с использованием указателей. Бинарная куча, напротив, имеет эффективную реализацию с использованием массива (именно из-за ограниченной структуры).

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