Java中的快速雙值優先隊列實現

Question

我正在尋找優先級隊列的實現，該優先級隊列使用常量double值作爲密鑰的優先級。我相信，如果執行得當，這可以比使用靈活比較器的默認PriorityQueue更快。 reduceKey操作（=減少已在隊列中的元素的優先級）是不必要的。

我發現了一個implementation from the NLP group in Stanford，但他們聲稱它是緩慢作爲原始實施的兩倍。是否有PQ實現可以勝過我們用例的默認PriorityQueue？

Answer 1

我們最終實現我們自己的堆結構。經過優化的remove()操作的d-ary堆表現得相當不錯，特別是在加載共享內存的機器上。

Answer 2

嘗試使用塞奇威克韋恩代碼在

http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html

但隨着雙取代通用密鑰類型和刪除可比/比較器代碼。

Answer 3

您引用的斯坦福大學NLP版本的速度較慢，因爲它支持decreaseKey（）。正如它的Javadoc中所提到的，你可以試試這個類，它不支持decreaseKey（）：

http://www.jarvana.com/jarvana/view/edu/stanford/nlp/stanford-corenlp/1.3.0/stanford-corenlp-1.3.0-javadoc.jar!/javadoc/edu/stanford/nlp/util/FixedPrioritiesPriorityQueue.html