如何在 Scala 中获取优先级队列的第 k 个最小元素？

Question

我尝试了以下但似乎是错误的！

import collection.mutable

object Main {
  def main(args: Array[String]): Unit = {
    val asc = Ordering.by((_: (Double, Vector[Double]))._1).reverse
    val pq = mutable.PriorityQueue.empty[(Double, Vector[Double])](asc)

    pq.enqueue(12.4 -> Vector(22.0, 3.4))
    pq.enqueue(1.2 -> Vector(2.3, 3.2))
    pq.enqueue(9.1 -> Vector(12.0, 3.2))
    pq.enqueue(32.4 -> Vector(22.0, 13.4))
    pq.enqueue(13.2 -> Vector(32.3, 23.2))
    pq.enqueue(93.1 -> Vector(12.0, 43.2))

    val k = 3

    val kthMinimum = pq.take(k).last
    println(kthMinimum)
  }
}

Answer 1

问题是 PriorityQueue 属性与继承的集合方法（如 take 等）之间的不兼容。Scala 集合的奇怪实现问题的另一个例子。

Java 的 PriorityQueue 存在同样的问题。

import java.util.PriorityQueue

val pQueue = new PriorityQueue[Integer]

pQueue.add(10)
pQueue.add(20)
pQueue.add(4)
pQueue.add(15)
pQueue.add(9)

val iter = pQueue.iterator()

iter.next() // 4
iter.next() // 9
iter.next() // 10
iter.next() // 20
iter.next() // 15

因此，PriorityQueue 在底层 ArrayBuffer 中维护您的数据（不完全是，而是一种特殊的继承 class）。这个“数组”保持堆放状态。并且继承的 take API 工作在这个堆化的类似数组的数据结构之上。最小堆化数组的前 k 个元素肯定与 minimum k 个元素不同。

现在，定义 a PriorityQueue 应该支持 enqueue 和 dequeue。它只是维护最高优先级（第一个）元素，并且无法可靠地提供队列中的第 k 个元素。

虽然我说这是 Java 和 Scala 实现的问题，但不可能为此提出一个合理的实现。我只是想知道为什么这些误导性方法仍然存在于 PriorityQueue 实现中。我们不能删除它们吗？

我强烈建议使用最严格的 API 适合您的要求。换句话说，坚持使用 Queue API 而不是使用继承的 API 方法（这可能会做一些奇怪的事情）。

虽然没有好的方法（因为它不是 PriorityQueue 明确要求的东西）。

您可以通过在时间复杂度为 k * log(n).

的循环中简单地 dequeueing k times 来实现此目的

val kThMinimum = {
  val pqc = pq.clone()
  (1 until k).foreach(i => pqc.dequeue())
  pqc.dequeue()
}

Answer 2

在Scala API doc中明确说明：

Only the dequeue and dequeueAll methods will return elements in priority order (while removing elements from the heap). Standard collection methods including drop, iterator, and toString will remove or traverse the heap in whichever order seems most convenient.

如果你想坚持使用PriorityQueue，似乎dequeue-ing k次或pq.dequeueAll(k-1)可能是实现优先检索的唯一方法。

如何在 Scala 中获取优先级队列的第 k 个最小元素？

How do I get the k-th minimum element of a Priority Queue in Scala?

scala

priority-queue