Почему сбалансированный BST не используется повсеместно над Binary Heap в изменяемых структурах?

Question

Мне кажется, что Binary Search Tree может делать все, что может делать Binary куча, плюс дополнительные вещи.

|                     |   Heap   | Bal. BST |
---------------------------------------------
| Lookup min element  |  O(1)    |  O(1)    |
---------------------------------------------
| Add an element      |  O(logn) |  O(logn) |
---------------------------------------------    
| Find and Remove     |  O(n)    |  O(logn) |
| an element          |          |          |
---------------------------------------------

В результате поиска и удаления свойств возможно мутировать элемент, и мы можем в значительной степени гарантировать, что порядок все еще сохраняется после мутации в O(logn) время

Преимущества, которые я вижу с помощью Binary Heap:

i) Проще реализовать ii) Выделенная память является непрерывной (и, следовательно, более быстрый доступ)

(i) не является проблемой, так как я редко буду реализовывать любой из них с нуля. Если мы часто мутируем элементы, то (ii) не является существенным преимуществом.

Мне кажется, что сбалансированное двоичное дерево может делать все, что может делать двоичная куча, тогда почему оно не используется повсеместно? (Например, двусвязные списки используются повсеместно над одиночными связанными списками)

Answer 1

Одна поправка, нахождение минимума составляет O(log(n)) для BST. Другие области, где куча имеет лучшие номера, чем BST. Добавление элемента в кучу на практике имеет ожидаемое значение O(1) (среднее значение составляет 2 сравнения), что лучше, чем BST. Превращение списка в кучу имеет время O(n), что опять же лучше, чем O(n log(n)) для BST.

И, наконец, вы ошибаетесь, считая производительность и непрерывную память необходимыми. Кучи обычно используются как способ реализации очередей с приоритетом, которые часто используются в критически важных для кода частях кода, таких как планировщики. Для крайнего примера рассмотрим планировщик в ядре вашей ОС. Более того, как только вы попадаете в ядро, абстракции, к которым вы привыкли обмениваться памятью, становятся явными. В результате в коде ядра часто требуется использовать структуры данных, которые используют физически непрерывную память. Что является значительным выигрышем для куч.

Answer 2

Для двоичных кучи:

• Упрощенная реализация является значительным преимуществом, поскольку она соответствует лучшей производительности - просто меньше кода для выполнения
• Непрерывная память является фантастическим преимуществом из-за уменьшения накладных расходов на выделение памяти и ссылочной локальности
• Значительно уменьшенное потребление памяти - еще одно важное преимущество, о котором вы не упомянули.

Кроме того, односвязные списки используются чаще, чем двусвязные списки в реальной работе. Часто они не являются строго списками, потому что мы пользуемся тем фактом, что односвязные списки могут иметь общие хвосты.

Answer 3

Сбалансированный BST имеет пространство не менее двух указателей на элемент (больше, если информация о балансе хранится отдельно). Это важно, когда предметы маленькие.