Используется структура очереди приоритетов?

Question

При поиске некоторых функций в документации по стандартной библиотеке C++ я читал, что push и pop для очередей приоритетов требуют постоянного времени.

http://www.cplusplus.com/reference/stl/priority_queue/push/

Константа (в priority_queue). Хотя обратите внимание, что push_heap работает в логарифмическом времени.

Мой вопрос в том, какая структура данных используется для поддержки очереди приоритетов с помощью O (1) для push и pop?

Answer 1

Я полагаю, вы имеете в виду cplusplus.com's page.

Ранее на странице говорится:

Эта функция член эффективно вызывает функцию-член push_back нижележащего объекта контейнера, а затем вызывает алгоритм push_heap, чтобы сохранить кучу свойство priority_queues.

Итак, после O(1) толчка, структура данных потеряла его свойство кучи инвариантной и тогда всегда следует, что с O(log N) вызова восстановить эту собственность. Другими словами, операция O(1) является лишь частью всей операции; полная операция равна O(1) + O(log N), что соответствует O(log N).

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

Answer 2

Нажмите и Pop работать в логарифмическом времени в соответствии с

http://www.cppreference.com/wiki/stl/priority_queue/pop

http://www.cppreference.com/wiki/stl/priority_queue/push

Answer 3

Я скептически отношусь к O (1) претензии ... где вы видите его?

В любом случае, здесь some notes on gcc's implementation of a priority queue.

Answer 4

Существует не такая куча. Они написали, что он вызывает push_heap, который является логарифмическим, поэтому он является logn.

Answer 5

Основным хранилищем для priority_queue может быть вектор или дека или что-либо подобное, которое поддерживает итераторы с произвольным доступом. Хранилище хранится как куча, который не является O (N) для push, поэтому я подозреваю, что вы это неправильно прочитали

Answer 6

Стандарт определяет эти элементы в терминах и pop_heap, что подразумевает компиляцию.

В случае, если that reference говорит, что это правда (он говорит, что top также является постоянным), почему никто не реализует сортировку O (N) общего назначения с использованием std::priority_queue?

На втором, хотя, это то, что ссылка может быть пытается сказать, в очень обманчивой образом: сложность в том, что из push_back O (1) + push_heap (O (журнал N))