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

Question

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

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

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

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

Answer 1

Полагаю, вы ссылаетесь на страницу cplusplus.com .

Ранее на странице написано:

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

Push и Pop запускаются в логарифмическом времени согласно

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

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