Может кто-нибудь объяснить асимптотическую сложность отсортированных и несортированных очередей с приоритетом?
Для отсортированного базового контейнера, почему для создания очереди приоритетов O (nlogn) требуется время, а для несортированного базового контейнера — только для создания O (n) времени? Кроме того, почему требуется (в отсортированном случае) O (nlogn) для сортировки очереди приоритетов?
В любом случае, есть ли полезные диаграммы, которые помогут мне понять время работы? В таких случаях быстрее использовать кучу?
Решение
Очередь приоритетов может быть реализована с помощью max-heap. И на самом деле, максимальная куча дает нам асимптотически оптимальную реализацию для очереди с приоритетами. Таким образом, в случае несортированного базового контейнера для создания очереди с приоритетами нам нужно только создать кучу из n элементов, что можно сделать с помощью Алгоритм Heapify за время В отсортированном случае мы должны полностью отсортировать элементы, которые известны как связанные с Theta (n).
Другие решения
Я думаю, что на ваш вопрос нельзя ответить вообще, так как нет единственного способа реализовать приоритетную очередь.
Это скорее определяется операциями, которые он может выполнять, и есть много способов его реализовать, куча или дерево AVL, просто имеющее некоторые возможности.
Вам нужно будет найти реализацию, выбранную реализацией STL, которую вы используете для ответа на этот вопрос.
В документации реализации SGI это гласит:
[2] Это ограничение является единственной причиной существования priority_queue в
все. Если важна итерация по элементам, вы можете использовать
вектор, который поддерживается в отсортированном порядке, или набор, или вектор, который
поддерживается как куча с использованием make_heap, push_heap и pop_heap.
Priority_queue, фактически, реализован как контейнер произвольного доступа
это поддерживается как куча. Единственная причина использовать контейнер
адаптер priority_queue вместо выполнения операций с кучей
вручную, чтобы дать понять, что вы никогда не выполняете
операции, которые могут нарушать инвариант кучи.
Так что, похоже, вы используете кучу, как вы и предлагали.