Эффективность STL priority_queue

Question

У меня есть приложение (C ++), которое, я думаю, будет хорошо обслуживаться STL priority_queue. В документации написано:

Priority_queue - это адаптер контейнера, что означает, что он реализован поверх некоторого базового типа контейнера. По умолчанию этот базовый тип является векторным, но другой тип может быть выбран явно.

и

Приоритетные очереди являются стандартной концепцией и могут быть реализованы многими различными способами; эта реализация использует кучи.

Ранее я предполагал , что top() равно O(1), и что push() будет O(logn) (две причины, по которым я выбрал priority_queue в первую очередь) - но документация не подтверждает и не опровергает это предположение.

Копая глубже, документы по концепции Последовательности говорят:

Сложности одноэлементной вставки и стирания зависят от последовательности.

priority_queue использует vector (по умолчанию) в качестве кучи, которая:

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

Я предполагаю, что по умолчанию priority_queue, top() равно O(1) и push() равно O(n).

Вопрос 1: Это правильно? (top() доступ O(1) и push() O(n)?)

Вопрос 2: Смогу ли я достичь O(logn) эффективности на push(), если бы я использовал set (или multiset) вместо vector для реализации priority_queue? Каковы будут последствия этого? Какие другие операции пострадают в результате?

N.B .: Я беспокоюсь об эффективности времени, а не пространства.

Answer 1

Адаптер очереди приоритетов использует стандартные алгоритмы кучи библиотеки для построения и доступа к очереди - это сложность тех алгоритмов, которые вы должны найти в документации.

Операция top () - это, очевидно, O (1), но, вероятно, вы хотите вызвать pop () кучи после вызова, которая (согласно Josuttis ) равна O (2 * log (N)) push () - это O (log (N)) - тот же источник.

И из стандарта C ++, 25.6.3.1, push_heap:

Сложность: максимум лог (последний - первый) сравнений.

и pop_heap:

Сложность: максимум 2 * лог (последнее - первое) сравнения.

Answer 2

top() - O (1) - так как он просто возвращает элемент @ front.

push() -

• вставить в вектор - 0 (1) амортизировано

• push_into_heap - самое большее, log (n) сравнений. O (LOGN)

  так что сложность push () - журнал (п)

Answer 3

Нет. Это не правильно. top () - это O (1), а push () - это O (log n). Прочтите примечание 2 в документации, чтобы увидеть, что этот адаптер не позволяет выполнять итерацию по вектору. Нил прав насчет pop (), но все же это позволяет работать с кучей, делая вставки и удаления за O (log n).

Answer 4

C ++ 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).

Answer 5

Если базовая структура данных представляет собой кучу, top () будет постоянным временем, а push (EDIT: и pop) будет логарифмическим (как вы говорите). Вектор просто используется для хранения таких вещей, как это:

КУЧА:
1
2 3
8 12 11 9

ВЕКТОР (используется для хранения)

1 2 3 8 12 11 9

Вы можете думать об этом как о элементе в позиции i, где дети являются (2i) и (2i + 1)

Они используют вектор, потому что он хранит данные последовательно (что гораздо эффективнее и кешируется, чем дискретный)

Независимо от того, как он хранится, всегда должна быть реализована куча (особенно богами, которые сделали библиотеку STD), чтобы pop был постоянным, а push - логарифмическим

Answer 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.