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

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

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

а также

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

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

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

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

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

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

Я предполагаю, что, используя default priority_queue , top() – это O(1) а push()O(n) .

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

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

NB: Меня беспокоит эффективность времени, а не пространство.

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

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

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

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

и pop_heap:

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

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

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

push()

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

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

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

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

VECTOR (используется для хранения)

1 2 3 8 12 11 9

Вы можете думать об этом как о элементе у детей положения i (2i) и (2i + 1)

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

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

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 .

Структурная структура данных 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). 
  • Выберите несколько полей из списка в Linq
  • Как избежать проблемы «слишком много параметров» в дизайне API?
  • Как реализовать карту с несколькими ключами?
  • Давайте будем гением компьютера.