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

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

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

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

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

и pop_heap:

Сложность: не более 2 * log (последнее - первое) сравнений.

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

push() -

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

• push_into_heap - не более log (n) сравнений. O (войти)

  поэтому сложность push () - log (n)

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

Если базовая структура данных представляет собой кучу, 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 - логарифмическим.

Базовая структура данных 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).

Q1: Я не смотрел в стандарт, но AFAIK, используя vector (или deque кстати), сложность будет 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 (не Sequence), но можно было бы использовать set для реализации очереди приоритетов с O(log n) push() и pop(). Однако это, вероятно, не превзойдет реализацию std::priority_queue по std::vector.