Разница между std:: set и std:: priority_queue

Поскольку оба std::priority_queue и std::set (и std::multiset) являются контейнерами данных, которые хранят элементы и позволяют вам получить доступ к ним упорядоченным образом и имеют такую же сложность вставки O(log n), каковы преимущества использования один над другим (или, какие ситуации требуют того или другого?)?

Хотя я знаю, что базовые структуры разные, меня не так сильно интересует разница в их реализации, поскольку я сравниваю их производительность и пригодность для различных целей.

Примечание. Я знаю об отсутствии дубликатов в наборе. Вот почему я также упомянул std::multiset, поскольку он имеет точно такое же поведение, что и std::set, но может использоваться там, где хранятся данные, которые можно сравнить как равные элементы. Поэтому, пожалуйста, не комментируйте проблему с одиночными/множественными ключами.

Ответ 1

Очередь приоритетов дает вам доступ к одному элементу в отсортированном порядке - то есть вы можете получить элемент с наивысшим приоритетом, а когда вы его удаляете, вы можете получить следующий наивысший приоритет и т.д. Очередь приоритетов также позволяет дублировать элементы, поэтому она больше напоминает мультимножество, чем набор. [Edit: Как заметил @Tadeusz Kopec, построение кучи также линейно по количеству элементов в куче, где построение набора - O (N log N), если оно не построено из последовательности, которая уже была заказана (в этом случае он также линейный).]

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

Ответ 2

std::priority_queue позволяет делать следующее:

Вставить элемент O(log n)
Получите самый маленький элемент O(1)
Сотрите самый маленький элемент O(log n)

в то время как std::set имеет больше возможностей:

Вставьте любой элемент O(log n), и константа будет больше, чем в std::priority_queue
Найдите любой элемент O(log n)
Найдите элемент,> = чем тот, который вы ищете O(log n) (lower_bound)
Удалить любой элемент O(log n)
Удалите любой элемент его iterator O(1)
Перейти к предыдущему/следующему элементу в отсортированном порядке O(1)
Получите самый маленький элемент O(1)
Получите самый большой элемент O(1)

Ответ 3

set/multiset обычно поддерживаются двоичным деревом. http://en.wikipedia.org/wiki/Binary_tree

priority_queue обычно поддерживается кучей. http://en.wikipedia.org/wiki/Heap_(data_structure)

Итак, вопрос в том, когда вы должны использовать двоичное дерево вместо кучи?

Обе структуры выложены в дереве, однако правила о взаимосвязи между anscestors отличаются.

Мы будем называть позиции P для родителя, L для левого ребенка и R для правого дочернего элемента.

В двоичном дереве L < P < R.

В куче P < L и P < R

Таким образом, бинарные деревья сортируют "боком" и кучи сортируют "вверх".

Итак, если мы рассматриваем это как треугольник, чем в двоичном дереве L, P, R полностью сортируются, тогда как в куче связь между L и R неизвестна (только их связь с P).

Это имеет следующие эффекты:

Если у вас есть несортированный массив и вы хотите превратить его в двоичное дерево, требуется время O(nlogn). Если вы хотите превратить его в кучу, требуется только время O(n) (поскольку оно просто сравнивается с поиском экстремального элемента)
Кучи более эффективны, если вам нужен только экстремальный элемент (самый низкий или самый высокий по некоторой функции сравнения). Кучи делают только сравнения (лениво), необходимые для определения экстремального элемента.
Двоичные деревья выполняют сравнения, необходимые для заказа всей коллекции, и сохраняют всю коллекцию, отсортированную за все время.
Кучи имеют постоянный поиск (peek) самого низкого элемента, бинарные деревья имеют логарифмический поиск по времени наименьшего элемента.

Ответ 4

Так как std::priority_queue и std::set (и std::multiset) являются контейнерами данных, которые хранят элементы и позволяют получить к ним доступ упорядоченным образом, и имеют одинаковую сложность вставки O(log n), каковы преимущества использования одного над другие (или какие ситуации требуют того или другого?)?

Хотя операции вставки и удаления для обоих контейнеров имеют одинаковую сложность O (log n), эти операции для std::set выполняются медленнее, чем для std::priority_queue. Это потому, что std::set выделяет много памяти. Каждый элемент std::set хранится в своем собственном распределении. std::priority_queue (с базовым контейнером std::vector по умолчанию) использует одно выделение для хранения всех элементов. С другой стороны, std::priority_queue использует много операций обмена над своими элементами, тогда как std::set использует только обмен указателей. Таким образом, если замена является очень медленной операцией для типа элемента, использование std::set может быть более эффективным. Кроме того, элемент может вообще не заменяться.

Затраты памяти на std::set намного больше, потому что он должен хранить много указателей между его узлами.