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

Admin 1
Viewed 353

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)
  }
}
priority-queue scala
2 Answers

It's explicitly stated in 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.

If you want to stick to using PriorityQueue, it seems dequeue-ing k times or pq.dequeueAll(k-1) might be the only means to achieve priority retrieval.

user_63165080

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()
}
user_11519290
Related