Scala排序的优先级队列始终始终以最低的数量作为头，升序 [英] Scala ordered priority queue that always has the lowest number as the head, ascending order

问题描述

我想获得一个代码示例，该代码示例完成优先级队列中项目的升序排序.

I'd like to get a code sample that accomplishes ascending ordering of items in a priority queue.

我想将Tuple2(Int, String)存储在优先级队列中，以便由元组的第一个元素以升序对其进行排序. 如果我的优先级队列称为pq，而我呼叫pq.head，我想获取具有最低编号的元组，与调用pq.dequeue相同.

I'd like to store Tuple2(Int, String) inside a priority queue so that it is ordered by the first element of the tuple in ascending order. If my priority queue is called pq and I call pq.head I'd like to get the tuple with the lowest number, same thing with calling pq.dequeue.

scala> val pq = scala.collection.mutable.PriorityQueue[(Int, String)]()
pq: scala.collection.mutable.PriorityQueue[(Int, String)] = PriorityQueue()

scala> pq += Tuple2(8, "eight")
res60: pq.type = PriorityQueue((8,eight))

scala> pq += Tuple2(4, "four")
res61: pq.type = PriorityQueue((8,eight), (4,four))

scala> pq += Tuple2(7, "seven")
res62: pq.type = PriorityQueue((8,eight), (4,four), (7,seven))

如何在插入以上内容时按第一元素的升序排序?

How to apply ascending ordering by first element at time of insertion to the above?

谢谢

推荐答案

PriorityQueue.apply和PriorityQueue.empty都采用一个隐式的Ordering实例，该实例将用于对内容进行排序-头部将是最大"值根据该顺序.您将获得元组的默认值，这是对元组元素的字典排序，这不是您想要的，因为它将使第一个元素最大的元组成为头部.

PriorityQueue.apply and PriorityQueue.empty both take an implicit Ordering instance that will be used to order the contents—the head will be the "largest" value according to that ordering. You're getting the default one for tuples, which is a lexicographic ordering on the elements of the tuple, which isn't what you want, since it'll make the tuple with the largest first element the head.

有两种方法可以解决此问题.最简单的方法是在队列上调用.reverse，这将为您提供一个内容相同但顺序相反的新队列，这意味着值最低的元组将是head.

There are a couple of ways you can solve this issue. The easiest is just to call .reverse on your queue, which will give you a new queue with the same contents but the opposite ordering, which means the tuple with the lowest value will be the head.

您还可以在创建队列时提供自己的排序:

You can also provide your own ordering when creating the queue:

import scala.collection.mutable.PriorityQueue

val pq = PriorityQueue.empty[(Int, String)](
  implicitly[Ordering[(Int, String)]].reverse
)

或者，如果您明确不希望查询第二个元素，则:

Or if you explicitly don't want the second element to be consulted:

val pq = PriorityQueue.empty[(Int, String)](
  Ordering.by((_: (Int, String))._1).reverse
)

这可能比反转队列更有效率，但可能不足以担心，因此您应该选择最感觉优雅的方法.

This is possibly a little more efficient than reversing the queue, but probably not enough to worry about, so you should just choose the approach that you find most elegant.

这篇关于Scala排序的优先级队列始终始终以最低的数量作为头，升序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！