我正在寻找一个优先级队列的实现，它使用常double量值作为键的优先级。我相信，如果实施得当，这可以比PriorityQueue使用灵活比较器的默认实施更快。不需要减少键操作（=降低队列中已有元素的优先级）。
我从斯坦福的 NLP 小组找到了一个实现，但他们声称它的速度是原始实现的两倍。是否有一个 PQ 实现可以胜过PriorityQueue我们用例的默认实现？
问问题
733 次
3 回答
0
我们最终实现了我们自己的堆结构。具有优化remove()操作的 d-ary 堆结果证明性能相当好，尤其是在加载的共享内存机器上。
于 2012-07-15T02:47:05.627 回答
0
尝试使用 Sedgewick-Wayne 代码
http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
但用 double 替换通用 Key 类型并删除 Comparable/Comparator 代码。
于 2012-06-26T10:44:37.843 回答
0
您引用的斯坦福 NLP 版本的速度较慢是因为它确实支持 reduceKey()。正如其 Javadoc 中所提到的，您可以尝试这个不支持 reduceKey() 的类：
于 2012-06-27T05:55:55.913 回答