scala - 在我的算法中替换命令式 PriorityQueue

Question

我目前有一种方法使用 scala.collection.mutable.PriorityQueue 按特定顺序组合元素。例如代码看起来有点像这样:

 def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
   val queue = new scala.collection.mutable.PriorityQueue[A]() ++ as
   while (queue.size > 1) {
     val a1 = queue.dequeue
     val a2 = queue.dequeue
     queue.enqueue(f(a1, a2))
   }
   queue.dequeue
 }

代码按编写的方式工作，但必须非常必要。我考虑过使用 SortedSet 而不是 PriorityQueue，但我的尝试使该过程看起来更加困惑。什么是做我想做的事情的更明确、更简洁的方式？

Answer 1

如果 f 不生成 Set 中已有的元素，您确实可以使用 SortedSet。 (如果是这样，您需要一个不可变的优先级队列。)执行此操作的声明方式是:

def process[A:Ordering](s:SortedSet[A], f:(A,A)=>A):A = {
  if (s.size == 1) s.head else {
    val fst::snd::Nil = s.take(2).toList
    val newSet = s - fst - snd + f(fst, snd)
    process(newSet, f)
  }
}