Scala优先级队列不维持顺序

Question

我希望这可以根据价格排序...

final case class Case(price: Int) {}

但这实际上是一个更大的案例类，我从中删除了字段。我想这样排序...

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

^按降序排序。

现在我希望这种排序保持不变...

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)

但是我的输出没有在第四和第五行排序...

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

而且，该foreach方法没有按顺序迭代...

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

打印...

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

如何使我的队列保持降序排列？

Answer 1

根据Scala文档，打印队列不会显示优先级：

仅dequeue和dequeueAll方法将按优先级顺序返回方法（同时从堆中删除元素）。标准的收集方法（包括drop，iterator和toString）将以最方便的顺序删除或遍历堆。

因此，尽管将首先打印最高优先级的元素，但是打印PriorityQueue不会显示元素的优先级顺序。要按顺序打印元素，必须复制PriorityQueue（例如，通过使用克隆），然后使它们出队

因此，如果您想按顺序查看元素，则需要这样的东西：

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)

或者您可以使用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)                     

根据此处的讨论 ，如果不通过出队破坏队列，就无法按顺序检索元素。这似乎是基础数据结构（二进制堆）的实现所固有的。