Scala：可以有效地使用 PriorityQueue.update 来减少键吗？
Scala: can PriorityQueue.update be used efficiently to decrease keys?
优先级队列支持'decrease key'操作（https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times），许多最佳优先搜索类型算法都需要它。它应该在 O(log n) 时间内 运行。 scala.collection.mutable.PriorityQueue 是否有效地支持这个？
查看 API 文档，我能找到的最接近的东西是
def update (idx: Int, elem: A) : Unit
Replaces element at given index with a new value.
但这有两个潜在的问题……首先，必须找到元素，但不清楚 findIndexOf 的时间复杂度是多少。* 第二，看起来 update 允许该值增加和减少；尚不清楚是否可以有效实施。
*参见例如How to implement O(logn) decrease-key operation for min-heap based Priority Queue? 证明这可以有效地完成。
有谁知道update的时间复杂度是多少？
scala.collection.mutable.PriorityQueue 不支持 decrease-key 操作。
要使用 decrease-key 操作实现 PQ，必须使用用于索引的附加数据结构来扩充典型的 PQ 实现。
您引用的 post 的已接受答案 How to implement O(logn) decrease-key operation for min-heap based Priority Queue 说明了如何执行此操作。
Java 标准库也不包含索引优先级队列。
您可以在 Princeton Algorithms 网站上找到一个 Java 实现。
上面有一个 Scala 版本 here
优先级队列支持'decrease key'操作（https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times），许多最佳优先搜索类型算法都需要它。它应该在 O(log n) 时间内 运行。 scala.collection.mutable.PriorityQueue 是否有效地支持这个？
查看 API 文档，我能找到的最接近的东西是
def update (idx: Int, elem: A) : Unit
Replaces element at given index with a new value.
但这有两个潜在的问题……首先，必须找到元素，但不清楚 findIndexOf 的时间复杂度是多少。* 第二，看起来 update 允许该值增加和减少；尚不清楚是否可以有效实施。
*参见例如How to implement O(logn) decrease-key operation for min-heap based Priority Queue? 证明这可以有效地完成。
有谁知道update的时间复杂度是多少？
scala.collection.mutable.PriorityQueue 不支持 decrease-key 操作。
要使用 decrease-key 操作实现 PQ，必须使用用于索引的附加数据结构来扩充典型的 PQ 实现。
您引用的 post 的已接受答案 How to implement O(logn) decrease-key operation for min-heap based Priority Queue 说明了如何执行此操作。
Java 标准库也不包含索引优先级队列。
您可以在 Princeton Algorithms 网站上找到一个 Java 实现。
上面有一个 Scala 版本 here