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

Question

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

Есть ли какие-либо преимущества для этого?

Answer 1

Конечно, мы можем. но со сбалансированным BST.

Минимум - самый левый элемент. Максимум самый правильный элемент. поиск этих элементов O(logn) каждый, и их можно кэшировать при каждой вставке / удалении после изменения структуры данных [обратите внимание, здесь есть место для оптимизации, но этот наивный подход также не противоречит требованию сложности!]

Таким образом вы получаете вставку, удаляете: O(logn), находите Мин. / Находите Макс.: O(1)

EDIT:
Единственное преимущество, которое я могу придумать в этой реализации, заключается в том, что вы получаете оба findMin, findMax в одной структуре данных.
Однако это решение будет намного медленнее [больше операций на шаг, ожидается больше кеш-ошибок ...] и будет занимать больше места, чем обычная реализация кучи на основе массива.

Answer 2

Да, но вы теряете O(1) среднюю вставку кучи

Как уже упоминалось, вы можете использовать BST для имитации кучи.

Однакоу этого есть один существенный недостаток: вы теряете среднее время вставки O (1), что, по сути, является единственной причиной использования кучи в первую очередь: https://stackoverflow.com/a/29548834/895245

Если вы хотите отслеживать как мин, так и макс.для кучи я рекомендую делать это с двумя кучами вместо BST, чтобы сохранить преимущество вставки O (1).

Answer 3

В принципе, я согласен с ответом @amit.Я более подробно расскажу о реализации этого модифицированного BST.

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

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

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

По моему мнению, обычно Heap можно заменить на сбалансированный BST, поскольку BST работает лучше почти во всех структурах данных кучи.Тем не менее, я не уверен, следует ли рассматривать Heap как устаревшую структуру данных.(Что ты думаешь?)

PS: Нужно дать перекрестную ссылку на разные вопросы: https://stackoverflow.com/a/27074221/764592

Answer 4

Да, мы можем, просто вставив и найдя минимум в BST.Однако преимуществ мало, поскольку поиск займет O (log n) времени, а другие функции получат аналогичные штрафы из-за более строгого порядка, применяемого по всему дереву.