Эффективность STL priority_queue
У меня есть приложение (С++), которое, я думаю, будет хорошо обслуживаться STL priority_queue. В документации говорится:
Priority_queue - это адаптер контейнера, что означает, что он реализован поверх некоторого базового типа контейнера. По умолчанию этот базовый тип является вектором, но явно может быть выбран другой тип.
и
Приоритетные очереди являются стандартной концепцией и могут быть реализованы различными способами; эта реализация использует кучи.
Ранее я предполагал, что top() - O(1), и что push() будет O(logn) (две причины, по которым я выбрал priority_queue), но документация не подтверждает и не отрицает это предположение.
Копая глубже, в документах для концепции Sequence говорится:
Сложности одноэлементной вставки и стирания зависят от последовательности.
В priority_queue используется vector (по умолчанию) как куча, которая:
... поддерживает произвольный доступ к элементам, постоянную вставку времени и удаление элементов в конце и линейную установку времени и удаление элементов в начале или в середине.
Я предполагаю, что по умолчанию priority_queue, top() есть O(1) и push() is O(n).
Вопрос 1: Правильно ли это? (top() доступ - O(1) и push() - O(n)?)
Вопрос 2:. Я мог бы достичь эффективности O(logn) на push(), если я использовал set (или multiset) вместо vector для реализации priority_queue? Каковы будут последствия этого? Какие другие операции могут пострадать в результате?
N.B.: Меня беспокоит эффективность времени, а не пространство.
Ответы
Ответ 1
Адаптер очереди приоритетов использует стандартные алгоритмы кучи библиотеки для создания и доступа к очереди - это сложность этих алгоритмов, которые вы должны искать в документации.
Операция top(), очевидно, O (1), но предположительно вы хотите поп() кучу после ее вызова, которая (согласно Josuttis) - O (2 * log (N)), а push() - O (log (N)) - тот же источник.
И из стандарта С++, 25.6.3.1, push_heap:
Сложность: не более, чем log (последний - первый).
и pop_heap:
Сложность: не более 2 * log (последний - первый) сравнения.
Ответ 2
Нет. Это неверно. top() - O (1), а push() - O (log n). Прочтите примечание 2 в документации, чтобы убедиться, что этот адаптер не позволяет выполнять итерацию через вектор. Нейл прав о pop(), но все же это позволяет работать с кучей, делающей вставки и удаления в O (log n) время.
Ответ 3
top() - O (1) - поскольку он просто возвращает элемент @спереди.
push() -
Ответ 4
Если базовая структура данных представляет собой кучу, top() будет постоянным временем, а push (EDIT: и pop) будет логарифмическим (как вы говорите). Вектор просто используется для хранения таких вещей, как это:
КУЧА:
1
2 3
8 12 11 9
ВЕКТОР (используется для хранения)
1 2 3 8 12 11 9
Вы можете думать об этом как о элементе в положении я children (2i) и (2i + 1)
Они используют вектор, потому что он хранит данные последовательно (что намного эффективнее и удобнее для кэширования, чем дискретный)
Независимо от того, как он хранится, куча всегда должна быть реализована (особенно боги, которые сделали STD lib), чтобы поп был постоянным, а push - логарифмическим
Ответ 5
С++ STL priority_queue базовая структура данных - это структура данных Heap (Heap - это нелинейный ADT, который на основе полного двоичного дерева и полного двоичного дерева реализуется через векторный (или массив) контейнер.
ex Input data : 5 9 3 10 12 4.
Heap (Considering Min heap) would be :
[3]
[9] [4]
[10] [12] [5]
NOW , we store this min heap in to vector,
[3][9][4][10][12][5].
Using formula ,
Parent : ceiling of n-1/2
Left Child : 2n+1
Right Child : 2n+2 .
Hence ,
Time Complexity for
Top = O(1) , get element from root node.
POP()= O(logn) , During deletion of root node ,there is chance to violation of heap order . hence restructure of heap order takes at most O(logn) time (an element might move down to height of tree).
PUSH()= O(logn) , During insertion also , there might chance to violation of heap order . hence restructure of heap order takes at most O(logn) time (an element might move up to root from leaf node).
Ответ 6
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 over std::vector.
