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

Ответ 1

Резюме

          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 против хэш-карты: Какая структура данных находится внутри std::map в C++?

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

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

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

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

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

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

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

С помощью этой настройки Buildroot на aarch64 ЦП HPI.

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

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

• Кучи поддерживают локальное свойство между родителем и прямым потомком (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 сбалансированы по высоте. Как правило, они не сбалансированы ни по весу, ни по мю для любого мю & lt; 1/2, то есть узлы-братья могут иметь очень разные числа потомков. "
• WAVL. В оригинальной статье упоминаются преимущества этой версии с точки зрения ограничений на операции балансировки и вращения.

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

Подобный вопрос по CS: https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Update

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

Ответ 5

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

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

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

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

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

Ответ 6

Другое использование BST над кучей; из-за важного различия:

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

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

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

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

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

Ответ 7

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

Ответ 8

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

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

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