Scala priority queue with in the order dequeue
2019, Nov 21
Scala library has priority queue implementation, but when priority are equal the dequeued items are not in the same order with enqueue order:
import scala.collection.mutable
class PriorityQueueTest{
implicit val ord: Ordering[(Any,Int)] = Ordering.by(_._2)
var queue = mutable.PriorityQueue[(Any,Int)]()
}
val pQueue = (new PriorityQueueTest())
val queue = pQueue.queue
queue.enqueue(("a",3))
queue.enqueue(("b",3))
queue.enqueue(("c",3))
queue.enqueue(("d",3))
queue.enqueue(("e",3))
println(queue)
//PriorityQueue((a,3), (b,3), (c,3), (d,3), (e,3))
queue.dequeue()
//res6: (Any, Int) = (a,3)
println(queue)
//PriorityQueue((e,3), (b,3), (c,3), (d,3))
queue.dequeue()
//res8: (Any, Int) = (e,3)
println(queue)
//PriorityQueue((d,3), (b,3), (c,3))
How to get the dequeue with same order:
import scala.collection.mutable
class PriorityQueueTest{
implicit val ord: Ordering[(Any,Int)] = Ordering.by(_._2)
var queue = mutable.PriorityQueue[(Any,Int)]()
def inplaceDeque(number:Int): Seq[(Any,Int)] ={
var res: Seq[(Any,Int)] = Seq()
res =queue.take(number).toSeq
queue =queue.drop(number)
res
}
}
val pQueue = (new PriorityQueueTest())
val queue = pQueue.queue
queue.enqueue(("a",3))
queue.enqueue(("b",3))
queue.enqueue(("c",3))
queue.enqueue(("d",3))
queue.enqueue(("e",3))
println(pQueue.queue)
// PriorityQueue((a,3), (b,3), (c,3), (d,3), (e,3))
pQueue.inplaceDeque(1)
// Seq((a,3))
println(pQueue.queue)
// PriorityQueue((b,3), (c,3), (d,3), (e,3))
Question
- Why Scala library doesn’t implement in order dequeue for priority queue?
- How to implement the Scala priority queue library?