Может кто-нибудь объяснить асимптотическую сложность отсортированных и несортированных очередей с приоритетом?

Для отсортированного базового контейнера, почему для создания очереди приоритетов O (nlogn) требуется время, а для несортированного базового контейнера — только для создания O (n) времени? Кроме того, почему требуется (в отсортированном случае) O (nlogn) для сортировки очереди приоритетов?

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

0

Решение

Очередь приоритетов может быть реализована с помощью max-heap. И на самом деле, максимальная куча дает нам асимптотически оптимальную реализацию для очереди с приоритетами. Таким образом, в случае несортированного базового контейнера для создания очереди с приоритетами нам нужно только создать кучу из n элементов, что можно сделать с помощью Алгоритм Heapify за время В отсортированном случае мы должны полностью отсортировать элементы, которые известны как связанные с Theta (n).

0

Другие решения

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

Это скорее определяется операциями, которые он может выполнять, и есть много способов его реализовать, куча или дерево AVL, просто имеющее некоторые возможности.

Вам нужно будет найти реализацию, выбранную реализацией STL, которую вы используете для ответа на этот вопрос.

В документации реализации SGI это гласит:

[2] Это ограничение является единственной причиной существования priority_queue в
все. Если важна итерация по элементам, вы можете использовать
вектор, который поддерживается в отсортированном порядке, или набор, или вектор, который
поддерживается как куча с использованием make_heap, push_heap и pop_heap.
Priority_queue, фактически, реализован как контейнер произвольного доступа
это поддерживается как куча. Единственная причина использовать контейнер
адаптер priority_queue вместо выполнения операций с кучей
вручную, чтобы дать понять, что вы никогда не выполняете
операции, которые могут нарушать инвариант кучи.

Так что, похоже, вы используете кучу, как вы и предлагали.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector