Куча или Красно-Черное Дерево?
Я готов использовать структуру данных в качестве буфера переполнения постоянного пространства. Я хочу иметь эффективную вставку, но самое главное эффективное удаление элемента min. Я думал об использовании кучи, так как у меня есть O (log (n)) find_min () и log (n) для вставки и удаления. С другой стороны, я знаю, что не понимаю преимущества по сравнению с красно-черным деревом, поскольку оно также имеет O (log (n)) для вставки и удаления, но и O (1) находит min / max. И преимущество отсортированного вывода (меня это не волнует).
Вопрос связан с:Является ли красно-черное дерево моей идеальной структурой данных?
Поскольку у меня есть обе структуры, доступные из std :: map и boost :: heap, почему я предпочитаю использовать кучу вместо красно-черного дерева?
Наконец, используя красно-черное дерево, у меня также есть O (log (n)) время поиска для записи, в то время как для кучи время O (n), что важно, поскольку существуют дубликаты.
Решение
Разница в первую очередь в том, как вы будете использовать структуры.
-
Двоичные кучи — это очень быстрые структуры данных для вставки значений и извлечения минимального значения. Однако они не поддерживают эффективный поиск или удаление случайных значений.
-
Красные / черные деревья — это сбалансированные двоичные деревья поиска, которые поддерживают эффективную вставку, удаление, поиск произвольных значений и (достаточно быстрый) минимум поиска. Тем не менее, они имеют много накладных расходов по сравнению с двоичной кучей.
Если все, что вам нужно, это вставка, поиск-минимум и удаление-минимум, бинарная куча, вероятно, является лучшим выбором, потому что издержки меньше, а время выполнения должно быть быстрее. Если вам нужно вставить и удалить произвольные значения или искать произвольные значения, вероятно, лучшим выбором будет красное / черное дерево. Как и во всех инженерных разработках, выбор правильной структуры данных — это все о компромиссах.
Также обратите внимание, что вы можете использовать std::priority_queue если вам нужна двоичная куча; Вам не нужно использовать Boost. Также не гарантируется, что std::map красное / черное дерево; это, вероятно, какой-то сбалансированный BST, но он может быть сбалансирован с использованием другого алгоритма.
Надеюсь это поможет!
Другие решения
Куча легко реализуется в смежной памяти, то есть в массиве. Красно-черное дерево обычно создается с отдельным выделением кучи для каждого узла. Красно-черное дерево получает доступ к памяти по всей куче для каждого обхода дерева. Это поведение кэша в худшем случае. Хотя алгоритмическая сложность некоторых операций одинакова для обеих структур, постоянные издержки для красно-черного дерева намного выше.