Приоритетная структура очереди используется?
При поиске некоторых функций в документации библиотеки стандарта C++ я считал то нажатие, и поп для приоритетных очередей требуется постоянное время.
http://www.cplusplus.com/reference/stl/priority_queue/push/
Постоянный (в priority_queue). Хотя уведомление, которым push_heap управляет в логарифмическое время.
Мой вопрос состоит в том, какая структура данных используется для поддержания приоритетной очереди с O (1) для нажатия и поп?
6 ответов
Полагаю, вы имеете в виду страницу cplusplus.com .
Ранее на странице говорится:
Эта функция-член эффективно вызывает функцию-член push_back базового объекта-контейнера, а затем вызывает алгоритм push_heap, чтобы сохранить свойство heap для priority_queues.
Таким образом, после нажатия O (1) структура данных потеряла свой инвариант свойства кучи и затем всегда будет следовать за ним с O (log N) позвоните по номеру , чтобы восстановить это свойство. Другими словами, операция O (1) - это только одна часть всей операции; полная операция O (1) + O (log N) , что совпадает с O (log N) .
Я предполагаю, что причина, по которой они упоминают это, заключается в том, что очередь с приоритетом является адаптером, и они пытаются подчеркнуть разницу между тем, что делает базовый контейнер, и тем, что делает адаптер.
Базовым хранилищем для priority_queue может быть вектор, двухсторонняя очередь или что-то подобное, которое поддерживает итераторы произвольного доступа. Хранилище поддерживается в виде кучи, что не является O (N) для push, поэтому я подозреваю, что вы прочитали это неправильно
Push и Pop выполняются за логарифмическое время согласно
Я скептически отношусь к утверждению O(1)... где вы это видели?
В любом случае, вот некоторые заметки о реализации очереди приоритетов в gcc.
Нет такой кучи. Они написали, что он вызывает push_heap, который является логарифмическим, поэтому он входит в систему.
Стандарт определяет эти элементы в термины push_heap и pop_heap , что подразумевает компилятивность.
Если то, что в этой ссылке , верно (в нем говорится, что top также является константой), то почему никто не реализует универсальную сортировку O (N) с использованием std :: priority_queue ?
Во-вторых, это то, что ссылка может пытаться сказать, очень вводя в заблуждение: сложность такая же, как у push_back O (1) + push_heap (O (журнал N))