在C++標準庫文檔中搜索某些函數時，我閱讀推送和彈出優先級隊列需要一段時間。使用優先級隊列結構嗎？
http://www.cplusplus.com/reference/stl/priority_queue/push/
常數（在priority_queue）。雖然注意到push_heap在對數時間運行。
我的問題是什麼樣的數據結構被用來維護一個優先級隊列與O（1）推和彈？根據
http://www.cppreference.com/wiki/stl/priority_queue/pop
http://www.cppreference.com/wiki/stl/priority_queue/push
我承擔你指的是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)相同。
我猜他們提到的原因是，優先級隊列是一個適配器，他們試圖強調底層容器與適配器的作用之間的區別。
Push和Pop運行對數時間？
在任何情況下，這裏是some notes on gcc's implementation of a priority queue。
我懷疑的O（1）要求......你在哪裏看到它
沒有這樣的堆。他們寫道，它調用push_heap，這是對數，所以它是logn。
priority_queue的底層存儲可以是支持隨機訪問迭代器的矢量或雙端隊列或任何類似的東西。存儲保持爲堆，這是不針對push O（N），所以我懷疑您已閱讀本錯
該標準定義了在push_heap和pop_heap，這意味着該術語compilexity那些成員。
如果that reference說的是真的（說top也是常量），爲什麼沒有人使用std::priority_queue實現通用的O（N）排序？
在第二雖然，這是個什麼可以參考想說，在一個非常誤導的方式：複雜是，push_back O（1）+ push_heap（O（日誌N））
你從哪裏讀到的？ – 2010-04-10 15:42:01
http://www.cplusplus.com/reference/stl/priority_queue/push/ – 2010-04-10 15:43:19