CODEWITHSUNDEEP
scaladata-structuresqueuepriority-queue
Michael Lafayette
Michael Lafayette

Reputation: 3072

Scala priority queue not maintaining ordering

I want this to be in order based on price...

final case class Case(price: Int) {}

But it's actually a significantly bigger case class that I removed fields from. I want to sort it like this...

val queue = PriorityQueue.empty[Case](Ordering.by((_: Case).price).reverse)

^ Sorted by descending price.

Now I want that sorting to stay...

queue.enqueue(Case(price = 2))
println(queue.toString)

queue.enqueue(Case(price = 3))
println(queue.toString)

queue.enqueue(Case(price = 4))
println(queue.toString)

queue.enqueue(Case(price = 1))
println(queue.toString)

queue.enqueue(Case(price = 0))
println(queue.toString)

But my output isn't sorted on the fourth and fifth line...

PriorityQueue(Case(2))
PriorityQueue(Case(2), Case(3))
PriorityQueue(Case(2), Case(3), Case(4))
PriorityQueue(Case(1), Case(2), Case(4), Case(3))
PriorityQueue(Case(0), Case(1), Case(4), Case(3), Case(2))

Also, the foreach method isn't iterating in order...

queue.foreach{ q =>
  print(q + ", ")
}

Prints...

Case(0), Case(1), Case(4), Case(3), Case(2),

How do I make my queue remain ordered on descending price?

Upvotes: 0

Views: 1301

Answers (3)

wherby
wherby

Reputation: 784

Yes, the scala default implementation is not inplace dequeue while the priority queue elements are equal. You could use implement the inplace dequeue as blow:

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

enter image description here

Upvotes: -1

evan.oman
evan.oman

Reputation: 5572

Per the Scala Documentation, printing the queue will not show the priority:

Only the dequeue and dequeueAll methods will return methods 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.

Therefore, printing a PriorityQueue will not reveal the priority order of the elements, though the highest-priority element will be printed first. To print the elements in order, one must duplicate the PriorityQueue (by using clone, for instance) and then dequeue them

Thus if you want to see the elements in order you will need something like this:

scala> val queue = PriorityQueue.empty[Case](Ordering.by((_: Case).price).reverse)
queue: scala.collection.mutable.PriorityQueue[Case] = PriorityQueue()

scala> queue += Case(2) += Case(3) += Case(4) += Case(1) += Case(0)
res1: queue.type = PriorityQueue(Case(0), Case(1), Case(4), Case(3), Case(2))

scala> while (queue.size > 0) println(queue.dequeue)
Case(0)
Case(1)
Case(2)
Case(3)
Case(4)

Or you can get the ordered collection using dequeueAll:

scala> val queue = PriorityQueue.empty[Case](Ordering.by((_: Case).price).reverse)
queue: scala.collection.mutable.PriorityQueue[Case] = PriorityQueue()

scala> queue += Case(2) += Case(3) += Case(4) += Case(1) += Case(0)
res2: queue.type = PriorityQueue(Case(0), Case(1), Case(4), Case(3), Case(2))

scala> val ordered = queue.dequeueAll                                                                      
ordered: scala.collection.immutable.IndexedSeq[Case] = Vector(Case(0), Case(1), Case(2), Case(3), Case(4)) 

scala> ordered.foreach(println)                                                                            
Case(0)                                                                                                    
Case(1)                                                                                                    
Case(2)                                                                                                    
Case(3)                                                                                                    
Case(4)

Based on discussions here, there is no way to retrieve the elements in order without destroying the queue via dequeuing. This seems to be intrinsic to the implementation of the underlying data structure (a binary heap).

Upvotes: 7

shaktimaan
shaktimaan

Reputation: 12092

Printing the priority queue may not return the elements in the order.

What is guaranteed though is that head always returns the lowest (as per your ordering) element and repeated dequeueing dequeues elements in the order specified by the Ordering.

When I do:

queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()

I see:

res10: Case = Case(0)
res11: Case = Case(1)
res12: Case = Case(2)
res13: Case = Case(3)
res14: Case = Case(4)

Upvotes: 1

Related Questions