Эффективность 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() -

вставить в вектор - 0 (1) амортизируется
push_into_heap - не более, log (n) сравнения. O (LOGN)

поэтому сложность 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.