Можем ли мы использовать двоичное дерево поиска для симуляции работы кучи?
Мне было интересно, можем ли мы использовать двоичное дерево поиска для имитации операций с кучей (вставка, поиск минимума, удаление минимума), т. Е. Использовать BST для выполнения той же работы?
Есть ли какие-либо преимущества для этого?
4 ответа
Мы можем точно. но со сбалансированным BST.
Минимум - самый левый элемент. Максимум самый правильный элемент. найти эти элементы O(logn) каждый, и может быть кэширован при каждой вставке / удалении, после изменения структуры данных [обратите внимание, здесь есть место для оптимизации, но этот наивный подход также не противоречит требованию сложности!]
Таким образом, вы получите вставку, удалите: O(logn), findMin / findMax: O(1)
РЕДАКТИРОВАТЬ:
Единственное преимущество, которое я могу придумать в этой реализации, состоит в том, что вы получаете оба findMin,findMax в одной структуре данных.
Тем не менее, это решение будет намного медленнее [больше операций на шаг, ожидается больше ошибок кэша...] и будет занимать больше места, чем обычная реализация кучи на основе массива.
Да, но вы теряете O(1) средняя вставка кучи
Как уже упоминалось, вы можете использовать BST для имитации кучи.
Однако у этого есть один существенный недостаток: вы теряете среднее время вставки O(1), что в основном является единственной причиной использования кучи в первую очередь: /questions/13541891/kucha-protiv-binarnogo-dereva-poiska-bst/13541892#13541892
Если вы хотите отслеживать как минимальное, так и максимальное значение в куче, я рекомендую делать это с двумя кучами вместо BST, чтобы сохранить преимущество вставки O(1).
Да, мы можем, просто вставив и найдя минимум в BST. Преимущества, однако, невелики, так как поиск займет O(log n) времени, а другие функции получат аналогичные штрафы из-за более строгого порядка, применяемого по всему дереву.
Я согласен с ответом @amit. Я более подробно остановлюсь на реализации этого модифицированного BST.
Куча может сделать findMin или же findMax в O(1), но не оба в одной структуре данных. С небольшой модификацией BST может findMin а также findMax в O(1).
В этом модифицированном BST вы отслеживаете узел min и узел max каждый раз, когда выполняете операцию, которая может потенциально изменить структуру данных. Например, в операции вставки вы можете проверить, больше ли минимальное значение, чем вновь вставленное значение, а затем назначить минимальное значение вновь добавленному узлу. Та же самая техника может быть применена к максимальному значению. Следовательно, этот BST содержит эту информацию, которую вы можете получить в O(1). (так же, как двоичная куча)
В этом BST (в частности, сбалансированный BST), когда вы pop min или же pop max следующее минимальное значение, которое должно быть назначено, является преемником минимального узла, тогда как следующее максимальное значение, которое должно быть назначено, является предшественником максимального узла. Таким образом, он выполняет в O(1). Благодаря комментарию @JimMischel, приведенному ниже, нам нужно перебалансировать дерево, поэтому оно все равно будет работать O(log n). (так же, как двоичная куча)
На мой взгляд, обычно Heap можно заменить на сбалансированный BST, поскольку BST работает лучше почти во всех структурах данных кучи. Тем не менее, я не уверен, следует ли рассматривать Heap как устаревшую структуру данных. (Как вы думаете?)
PS: приходится ссылаться на разные вопросы: /questions/13541891/kucha-protiv-binarnogo-dereva-poiska-bst/13541899#13541899