有人可以解釋排序和未排序的優先級隊列的漸近複雜性嗎？

對於已排序的基礎容器，爲什麼需要創建優先級隊列O（nlogn）時間，但對於未排序的基礎容器，只需要O（n）次創建？另外，爲什麼需要（在排序的情況下）O（nlogn）對優先級隊列進行排序？有人可以解釋排序和未排序的優先級隊列的漸近複雜性嗎？

無論哪種情況，是否有幫助我理解運行時間的有用圖表？在這些情況下使用堆更快嗎？

2013-02-13 Bob John

'歐米茄（nlogn）'是一種經過驗證的排序下限（使用基於比較的算法）。由於您可以使用「排序優先級隊列」進行排序，因此無法打敗此限制。 – amit 2013-02-13 11:21:49

@amit：我thik我可以排序O（1）中的SORTED列表，因爲這似乎是一個問題：「爲什麼需要（在排序的情況下）O（nlogn）排序優先隊列？」 – mikyra 2013-02-13 11:25:12

@mikyra但是這個問題並沒有詢問關於排序的*輸入*它要求排序的*底層容器* - 這意味着你需要對你得到的輸入進行排序，即'歐米茄（nlogn）' – amit 2013-02-13 12:50:35

可以用最大堆實現優先級隊列。事實上，最大堆給我們優先級隊列的漸近最優實現。因此，在未排序的底層容器的情況下，爲了創建一個優先級隊列，我們只需要在n個元素中創建一個堆，這可以在O（n）時間內用Heapify algorithm完成。在排序的情況下，我們需要對已知爲Theta（n）的元素進行完全排序。

來源

2013-02-13 11:34:03 eladidan

我認爲你的問題不能一般回答，因爲沒有一種方法可以實現優先級隊列。

它是由它能夠執行的操作定義的，並且有很多方法來實現它，堆或AVL樹只是提供了一些可能性。

您將不得不查找您正在用來回答此問題的STL實現選擇的實現。

在SGI實現它讀取的文檔：

[2]這限制爲priority_queue在所有存在的唯一原因。如果迭代遍歷元素很重要，則可以使用以排序順序維護的向量或使用make_heap，push_heap和pop_heap將集合維護爲堆的向量。實際上，Priority_queue實現爲隨機存取容器，它被維護爲堆。使用容器適配器priority_queue（而不是手動執行堆操作）的唯一原因是明確指出，您從不執行任何可能違反堆不變性的操作。

所以它似乎只是使用堆，因爲你建議。

來源

2013-02-13 11:36:29 mikyra

有人可以解釋排序和未排序的優先級隊列的漸近複雜性嗎？

回答

相關問題