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

I tried the following but it seems to be wrong!

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)
  }
}

Solution

The problem is the incompatibility between PriorityQueue properties and inherited collection methods like take etc. Another example of weird implementation issues with Scala collections.

Same problems exist with Java's 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

So, PriorityQueue maintains your data in an underlying ArrayBuffer (not exacltly but an special inherited class). This "Array" is kept heapified. And the inherited take API works on top of this heapified Array-like data structure. And first k elements of a min-heapified Array are certainly not same as minimum k elements.

Now, definition a PriorityQueue is supposed to support enqueue and dequeue. It just maintains the highest priotiry (first) element and is just incapable of reliably providing k-th element in the queue.

Although I say that this is a problem with both Java and Scala implementations, its just not possible to come up with a sane implemention for this. I jsut wonder that why are these misleading methods still present in PriorityQueue implementations. Can't we just remove them ?

I strongly suggest staying with the strictest API suited for your requirement. In other words stick with Queue API and not using the inherited API methods (which might do weird things).

Although, there is no good way of doing it (as it is not something explicitly required for a PriorityQueue).

You can achieve this by simply dequeueing k times in a loop with time complexity of k * log(n).

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