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

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

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

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

Резюме

          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)

Источники:

• Документ: 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)по той же причине. Но если вы хотите это сделать, вполне вероятно, что вы захотите поддерживать дополнительный индекс в актуальном состоянии для операций с кучей. Как реализовать операцию уменьшения ключа 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

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

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

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

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

Как уже упоминалось, 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.

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

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

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

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

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

Другое использование 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) времени.

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

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

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

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