Java中的優先隊列

Question

java.util.PriorityQueue允許Comparator在施工時通過。插入元素時，它們按照比較器指定的優先級排序。

元素的優先級在插入後會發生什麼變化？ PriorityQueue重新排序元素是什麼時候？是否可以輪詢實際上沒有最低優先級的元素？

是否有優先級隊列的好實現允許高效的優先級更新？

Answer 1

您應該刪除該元素，對其進行更改並重新插入，因爲插入時會發生排序。雖然它涉及幾個步驟，但它是有效的可能是足夠好的。 （我剛剛注意到有關刪除的註釋是O（n）。）

一個問題是，它也會在您刪除元素時重新排序，如果您剛剛重新插入元素後來。如果從零開始實現自己的優先級隊列，則可以使用update（）來跳過此步驟，但是擴展Java的類將不起作用，因爲您仍然僅限於基本提供的remove（）和add（）。

Answer 2

我期望的PriorityQueue不重新排序的東西 - 如果它試圖做一個二進制搜索找到把任何新的條目正確的地方就可以得到非常困惑。

一般來說，我希望改變已經在隊列中的東西的優先級是一個壞主意，就像改變組成哈希表中的鍵的值一樣。