Priority Queue刪除複雜時間

Java中Priority Queue類的remove()函數的複雜性（大哦）是什麼？我無法在任何地方找到任何記錄，我認爲它是O（n），考慮到在刪除它之前必須先找到該元素，然後重新組合樹。但我看到其他人不同意並認爲它是O（logn）。有任何想法嗎？Priority Queue刪除複雜時間

來源

2012-10-04 samturner

您是否考慮閱讀Javadoc？ [「這個實現提供了enqueing和dequeing方法（offer，poll，remove（）和add）的O（log（n））時間」]（http://docs.oracle.com/javase/6/docs/api /java/util/PriorityQueue.html）。 – EJP

是的，我做到了。在下一行中，它表示「刪除（對象）和包含（對象）方法的線性時間;和檢索方法（peek，element和size）的持續時間「，這是我感到困惑的地方。我想我現在明白了。 – samturner

的測試remove複雜度爲O（N），因爲包含了複雜度爲O（N）（在Java中的優先級隊列類）

一種方式自己優先這可以由O（logN）的隊列實現是維護一個像HashMap一樣的輔助數據結構，它將映射從優先級隊列中的值維持到隊列中的位置。所以，在任何時候 - 你都會知道任何價值的指數位置。

請注意，此修改不會影響任何現有操作的運行時間 - 您只需要在heapify操作期間更新映射。

來源

2014-02-28 05:29:42 Hari

因此，如果我知道元素的索引位置，如何根據索引在優先級隊列API中刪除它？（在O（logN）時間） – novalain

@novalain不幸的是，Java API沒有提供通過索引訪問優先級隊列中的元素的方法，因此您必須使用自己的自制構建的優先級隊列實現。 –

爲什麼O（logN）從我們自己的實現中移除而不是O（1）？我確定我錯過了一些細節，但優先級隊列只是一個按高優先級排序的數據結構。如果它是使用鏈表實現的，並且我們知道索引，那麼我們不能只刪除該元素並將前一個節點連接到下一個節點？ – user3125693

根據Oracle文檔：「實現注意事項：此實現提供O（日誌（n））的時間入隊和dequeing方法（報價，民意調查顯示，刪除（）和補充）;線性時間remove（Object）和contains（Object）方法;以及檢索方法（peek，element和size）的常量時間。「

Link here to Oracle Doc

來源

2015-09-22 12:03:55

我認爲他的意思是remove（object）不是remove（），第一個是O（n），後一個是O（log n） –

remove（）和poll（）除了缺少元素語義外都是一樣的。刪除特定項目（'remove（Object）'）是'O（n）'。我認爲這個問題並不清楚，這也是一個有效的答案。 – TWiStErRob

的混亂實際上是由你的「刪除」功能引起的。在java中，有兩個刪除功能。

remove（） - >這是刪除頭/根，它需要O（logN）時間。
remove（Object o） - >這是刪除任意對象。找到這個對象需要O（N）時間，並且移除它需要O（logN）時間。

來源

2016-08-23 04:54:24 Chen

Priority Queue刪除複雜時間

回答

相關問題