Куча против двоичного дерева поиска (BST)

Куча просто гарантирует, что элементы на более высоких уровнях больше (для max-heap) или меньше (для min-heap), чем элементы на более низких уровнях, тогда как BST гарантирует порядок (от «левого» к «правому»). Если вам нужны отсортированные элементы, используйте BST.

Когда использовать кучу, а когда использовать BST

Куча лучше подходит для findMin / findMax (O(1)), тогда как BST хорош для всех находок (O(logN)). Вставка O(logN) для обеих структур. Если вас интересует только findMin / findMax (например, связанный с приоритетом), используйте кучу. Если вы хотите, чтобы все было отсортировано, используйте BST.

Первые несколько слайдов из здесь очень ясно объясняют вещи.

Как упоминалось другими, Heap может выполнять findMin или findMax в O (1), но не оба в одной структуре данных. Однако я не согласен с тем, что Heap лучше в findMin / findMax. Фактически, с небольшими изменениями, BST может выполнять оба findMin и findMax в O (1).

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

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

Мне было бы интересно услышать вашу мысль в комментарии ниже. Спасибо :)

Обновлять

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

Бинарное дерево поиска использует определение: для каждого узла узел слева от него имеет меньшее значение (ключ), а узел справа от него имеет большее значение (ключ).

Где в качестве кучи, будучи реализацией двоичного дерева, используется следующее определение:

Если A и B - узлы, где B - дочерний узел A, тогда значение (ключ) A должно быть больше или равно значению (ключу) B. То есть ключ (A) ≥ key (B ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Сегодня я задавал тот же вопрос на экзамене, и я понял его правильно. улыбка ... :)

Другое использование BST вместо кучи; из-за важной разницы:

• поиск преемника и предшественника в BST займет время O (h). (O (logn) в сбалансированном BST)
• в то время как в куче, потребуется O (n) времени, чтобы найти преемника или предшественника некоторого элемента.

Использование BST в куче. Допустим, мы используем структуру данных для хранения времени посадки рейсов. Мы не можем запланировать рейс на посадку, если разница во времени посадки меньше "d". И предположим, что многие рейсы запланированы для приземления в структуре данных (BST или Heap).

Теперь мы хотим запланировать еще один рейс, который приземлится в t. Следовательно, нам нужно вычислить разницу t с его преемником и предшественником (должно быть> d). Таким образом, для этого нам понадобится BST, который делает это быстро, т.е. за O (logn), если сбалансировано.

ИЗМЕНЕНО:

Сортировка BST занимает O (n) времени для печати элементов в отсортированном порядке (Inorder Traversal), в то время как Heap может сделать это за O (n logn) времени. Куча извлекает минимальный элемент и повторно заполняет массив, что заставляет его выполнять сортировку за время O (n logn).

Вставка всех n элементов из массива в BST занимает O (n logn). n элементов в массиве могут быть вставлены в кучу за O (n) раз. Что дает куче несомненное преимущество

Куча просто гарантирует, что элементы на более высоких уровнях больше (для max-heap) или меньше (для min-heap), чем элементы на более низких уровнях.

Мне нравится приведенный выше ответ, и я помещаю свой комментарий только в соответствии с моими потребностями и использованием. Мне пришлось получить список n местоположений, чтобы найти расстояние от каждого местоположения до конкретной точки, скажем (0,0), а затем вернуть местоположения a m, имеющие меньшее расстояние. Я использовал очередь приоритетов, которая является кучей. Для определения расстояний и помещения в кучу мне потребовалось n (log (n)) n местоположений log (n) на каждую вставку. Тогда для получения m с кратчайшими расстояниями потребовалось m (log (n)) m-location log (n) удалений скопления.

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