Эффективность STL priority_queue
У меня есть приложение (C++), что я думаю, был бы хорошо подан STL priority_queue. В документации говорится:
Priority_queue является контейнерным адаптером, означая, что он реализован сверху некоторого базового контейнерного типа. По умолчанию тот базовый тип является вектором, но другой тип может быть выбран явно.
и
Приоритетные очереди являются стандартным понятием и могут быть реализованы по-разному; эта реализация использует "кучу".
Я ранее принял это top() O(1), и это push() был бы a O(logn) (две причины я выбрал priority_queue во-первых) - но документация не подтверждает и не отклоняет это предположение.
Роя глубже, в документах для понятия Последовательности говорится:
Сложности одноэлементной вставки и стирания являются зависимым последовательности.
priority_queue использование a vector (по умолчанию) как "куча", который:
... произвольный доступ поддержек к элементам, постоянной вставке времени и удалению элементов в конце, и линейной вставке времени и удалению элементов вначале или в середине.
Я вывожу что, с помощью значения по умолчанию priority_queue, top() O(1) и push() O(n).
Вопрос 1: это корректно? (top() доступ O(1) и push() O(n)?)
Вопрос 2: я смог бы достигнуть O(logn) эффективность на push() если я использовал a set (или multiset) вместо a vector для реализации priority_queue? Что последствия имели бы выполнение этого? Что другие операции перенесли бы как следствие?
N.B.: я волнуюсь по поводу эффективности времени здесь, не располагают с интервалами.
5 ответов
Адаптер приоритетной очереди использует алгоритмы кучи стандартной библиотеки для построения и доступа к очереди - сложность этих алгоритмов вам следует искать в документации.
Операция top(), очевидно, O(1), но, предположительно, вы хотите после ее вызова выполнить pop() кучи, что (согласно Josuttis) составляет O(2*log(N)), а push() составляет O(log(N)) - тот же источник.
И из стандарта C++, 25.6.3.1, push_heap :
Сложность: Не более log(last - first) сравнений.
and pop_heap:
Complexity: Не более 2 * log(last - first) сравнений.
Нет. Это неверно. top() - это O(1), а push() - O(log n). Прочитайте примечание 2 в документации, чтобы увидеть, что этот адаптер не позволяет выполнять итерации по вектору. Нил прав насчет pop(), но все же это позволяет работать с кучей, выполняя вставки и удаления за время O(log n).
Если базовой структурой данных является куча, top() будет иметь постоянное время, а push (EDIT: и pop) будет логарифмическим (как вы и говорите). Вектор просто используется для хранения этих вещей вот так:
HEAP:
1
2 3
8 12 11 9
ВЕКТОР (используется для хранения)
1 2 3 8 12 11 9
Вы можете думать об этом как об элементе в позиции i, дочерними элементами которого являются (2i) и (2i+1)
Они используют вектор, потому что он хранит данные последовательно (что намного эффективнее и удобнее для кэша, чем дискретный)
Независимо от того, как они хранятся, куча всегда должна быть реализована (особенно богами, создавшими STD lib) так, чтобы pop был постоянным, а push - логарифмическим
top() - O(1) -- так как он просто возвращает элемент @ front.
push() -
- insert into vector - 0(1) amortized
push_into_heap - максимум, log(n) сравнений. O(logn)
поэтому сложность push() составляет... log(n)
Q1: Я не смотрел в стандарт, но AFAIK, используя vector (или deque btw), сложность будет O(1) для top(), O(log n) для push() и pop(). Я однажды сравнивал std::priority_queue с моей собственной кучей с O(1) push() и top() и O(log n) pop(), и это, конечно, было не так медленно, как O(n).
Q2: set не подходит в качестве базового контейнера для priority_queue (не последовательность), но можно использовать set для реализации очереди приоритетов с O(log n) push() и pop(). Однако это, вероятно, не превзойдет std::priority_queue по сравнению с std::vector реализацией.