Зачем использовать кучу над красно-черным деревом?

Question

Зачем использовать кучу над красно-черным деревом?

Очевидное отличие состоит в том, что красно-черное дерево может поддерживать удаление O(logn) по сравнению с удалением O(n) в куче.

Тем не менее, похоже, что все операции для красно-черного дерева выполняются быстрее / равны куче. Итак, мой вопрос: почему мы используем кучу поверх красно-черного дерева? Мне кажется, что красно-черное дерево может делать все, что может куча, но быстрее / равно.

Благодарю.

3

data-structures tree heap red-black-tree red-black-tree-insertion

Источник

user5781521 21 мар '19 в 05:59

1 ответ

Другие вопросы по тегам data-structures tree heap red-black-tree red-black-tree-insertion

user424499 23 май '22 в 02:46 2022-05-23 02:46 · Answer 1 · 2022-05-23 02:46

Основным вариантом использования minheap является приоритетная очередь, в которой выполняются основные операции push(newval), pop_smallest(), inspect_smallest().

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

Кроме того, хотя и Red Black Trees, и Minheaps имеют время вставки и удаления O(log n), постоянный коэффициент меньше для minheaps.

Кроме того, кучи можно представить гораздо более компактно, чем для красно-черного дерева. Нет необходимости в бите «раскраски», а само дерево легко представить в виде массива, поэтому нет необходимости хранить указатели.

Короче говоря, если приложение не нуждается в общем поиске и вместо этого может сосредоточиться на наименьшем значении, то куча представляет собой более простую и дешевую альтернативу.