Разница между 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 позволяет делать следующее:

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

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

  1. Вставьте любой элемент O(log n), и константа будет больше, чем в std::priority_queue
  2. Найдите любой элемент O(log n)
  3. Найдите элемент,> = чем тот, который вы ищете O(log n) (lower_bound)
  4. Удалить любой элемент O(log n)
  5. Удалите любой элемент его iterator O(1)
  6. Перейти к предыдущему/следующему элементу в отсортированном порядке O(1)
  7. Получите самый маленький элемент O(1)
  8. Получите самый большой элемент 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 намного больше, потому что он должен хранить много указателей между его узлами.