這個問題在這里已經有了答案： 堆插入的 O(1) 平均情況復雜度的引數 1 個回答 為什么 std::priority_queue::emplace 是對數的？ (2 個回答) 14 小時前關閉。
在對檔案std::priority_queue各國的復雜push操作：
比較的對數數加上 的復雜度
Container::push_back。
默認情況下std::vector用作底層容器。但是，push_back只能將元素推到向量的末尾，而在優先級佇列中，可能需要在向量中間的某處添加元素，在這種情況下，必須將后面的所有元素向右移動。在最壞的情況下，在開始添加元素時，推送操作將產生完整的 O(n) 成本。那么優先級佇列是如何在對數時間內做到的呢？為什么它默認使用向量而不是一些“簡單的插入和查找”容器，例如堆？
uj5u.com熱心網友回復：
而在優先級佇列中，可能需要在向量中間的某處添加元素，在這種情況下，后面的所有元素都必須向右移動
不會。不會發生右移。
新元素添加到末尾，在索引處i：O(1)
然后將其優先級與其在索引處的父級進行比較，i/2如果優先級更高，則進行交換。
如果發生交換，則比較下一個parent。
重復以上 2 個步驟，直到在索引處0。O(log(i))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/331762.html
上一篇：生成具有頂點和索引的球體？