Ответ 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), чтобы найти максимум, BSTO(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