2

我想知道为什么 Java 的优先级队列不支持 ChangePriority。我在某处（没有详细信息）读到，放弃 ChangePriority 允许人们使用更有效的实现，但不知道它怎么可能——二进制堆似乎非常简单/高效的数据结构——看不到任何改进的空间。另一个线索可能是它可能需要笨拙的界面来向 PQ 指示哪个元素（可能是堆中的位置）改变了它的优先级，但我仍然是 Java 的新手，无法得出结论。

编辑：为什么这不是一个毫无意义的问题？如果您是 Java 新手（尤其是 C/C++ 背景），您会开始想知道所有指针都去了哪里，或者我如何在 Java 中实现 Dijkstra 等。

第一个问题已经回答了很多次，据我所知，第二个问题没有一个简单的答案。人们可以期望，在像 Java 这样的语言中，所有常用的编程工具都在手边，开箱即用，封装在一个漂亮的类包装器中。但是突然之间你必须自己实现一个带有减少键方法的 PQ，这在 Java 中可能比在 C/C++ 中更尴尬。在这个问题中，我不是在问如何实现 Dijkstra（这在其他一些线程中得​​到了很好的回答）。如果没有减少键/优先级方法，仍然可能有许多 PQ 应用无法解决，例如。如果优先级更新比 PQ 中的项目多得多。在 Dijkstra 中最多有 V

因此，人们可能会认为 Java 的 PQ 缺乏变更优先级是有一些严重的原因的。不管实际的 Java 的 PQ 接口如何，这些原因本身可能很有趣。

4

2 回答 2

2

我怀疑设计选择是因为它是一个Queue. 队列的基本操作是入队和出队。APriority Queue的不同之处在于，作为入队操作的一部分，它允许一个元素优先于其他元素。大多数Queue实现不允许在放入元素后对其进行操作，尽管有些实现提供了peek功能。所以我们的数据类型是一个队列，我并不是真的“应该”搞乱内部安排，我本身也不应该关心。如果我使用队列，我基本上想要先进先出的行为。队列

话虽如此，您如何实现您想要的行为？我会推荐一个TreeMap. 它为您提供了类似队列的功能，我可以通过firstKey()or获取第一个或最后一个元素lastKey()，同时仍然通过我自己的界面提供人工排序Comparator以及通过 a 访问条目Key，尽管您的Key实现必须同时提供唯一标识符作为以及它的排序顺序。

于 2015-08-19T13:02:15.097 回答
0

虽然我无法确定为什么没有公开更改优先级方法PriorityQueue，但可以观察到，当对象的优先级PriorityQueue发生更改时，您可以简单地删除并重新插入该对象。

存在这种行为是PriorityQueue因为每当将新对象插入队列时，它都会被放置在适当的位置（基于对象的比较器）。这很有效，因为每次从队列中拉出某些东西时，都不需要重新计算来找到具有最小/最大优先级的元素。这带来了对象的优先级一旦被插入队列就不能改变的限制。

确实，删除和重新插入对象的速度较慢，可以看出代码的整体运行时复杂性仍然保持不变。也就是说，如果您有兴趣查看优先级队列的自定义 java 实现，这可能是一个很好的起点 - http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

于 2015-08-19T12:40:16.633 回答