Резюме
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 для отслеживания самого большого элемента и обновлять его всякий раз, когда этот элемент может быть изменен: при вставке большего свопа, при удалении найдите второе по величине. Можем ли мы использовать двоичное дерево поиска для имитации операции с кучей? (упоминается у Yeo ).
На самом деле, это ограничение куч по сравнению с BST: эффективный поиск only - поиск самого большого элемента.
Средняя вставка двоичной кучи составляет 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 Мбит / с), твердотельный накопитель: Samsung MZVLB512HAJQ-000L7 (512 ГБ, 3000 МБ / с)
Так ясно:
Время вставки кучи в основном постоянное.
Мы ясно видим точки изменения размера динамического массива. Поскольку каждые 10 тыс. Вставок мы усредняем, чтобы вообще видеть что-либо выше системного шума , эти пики на самом деле примерно в 10 тыс. Раз больше, чем показано!
Увеличенный график исключает, по существу, только точки изменения размера массива и показывает, что почти все вставки попадают под 25 наносекунд.
BST является логарифмическим. Все вставки намного медленнее, чем вставка средней кучи.
BST против подробного анализа hashmap по адресу: Какая структура данных находится внутри 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 вставки), но дает более мощные поиски (регистрация n поиска).
Кучи поддерживают локальное свойство между родителем и прямым потомком (parent> children).
Верхняя нота кучи - это большой элемент, который требует только местных знаний (зная вашего родителя).
Двусвязный список
Двусвязный список можно рассматривать как подмножество кучи, где первый элемент имеет наибольший приоритет, поэтому давайте сравним их и здесь:
- вставка:
- позиция:
- двусвязный список: вставленный элемент должен быть первым или последним, поскольку у нас есть только указатели на эти элементы.
- двоичная куча: вставленный элемент может оказаться в любой позиции. Менее ограниченный, чем связанный список.
- время:
- двусвязный список:
O(1) худший случай, поскольку у нас есть указатели на элементы, а обновление действительно простое
- двоичная куча:
O(1) среднее значение, таким образом, хуже, чем связанный список. Компромисс для более общей позиции вставки.
- поиск:
O(n) для обоих
Вариант использования этого - случай, когда ключом кучи является текущая временная метка: в этом случае новые записи всегда будут идти в начало списка. Таким образом, мы можем вообще забыть точную метку времени и просто сохранить позицию в списке в качестве приоритета.
Это можно использовать для реализации LRU-кеша . Точно так же, как для приложений кучи, таких как Dijkstra , вы захотите сохранить дополнительную хэш-карту от ключа до соответствующего узла списка, чтобы найти, какой узел быстро обновлять.
См. Также
Аналогичный вопрос по CS: https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap