使用 Stack[A] 的 PriorityQueue 非默认排序的 Scala 问题

Question

我正在尝试使用 Scala 编写耐心排序的简单实现。
我已经正确地创建了初始桩；然而，我使用优先级队列来简化输出列表的生成让我很头痛。

看来我的排序实现要么是错误的，要么被忽略了：

def PileOrdering = new Ordering[Stack[A]] {
    def compare(a : Stack[A], b : Stack[A]) = a.head.compare(b.head)
}

// Use a priority queue, ordering on stack heads (smallest stack elems)
val pq = new PriorityQueue[Stack[A]]()(PileOrdering)

// piles is a List[Stack[A]]
pq ++= piles

// Extract an ordered list of elements
val returnVal = (0 until count) map (_ => {
    val smallestList = pq.dequeue
    val smallestVal = smallestList.pop

    if (smallestList.length > 0){
        pq.enqueue(smallestList)
    }

    smallestVal
})

PriorityQueue 似乎是按（我想象是默认的堆栈排序）堆栈大小排序的，而不是我的排序。

有什么明显错误的地方吗？ 任何帮助将不胜感激。
谢谢，

编辑：我在原来的问题中没有说清楚：我正在使用 Scala 2.8.1。
Edit2：我期望 returnVal 包含从最小到最大的元素顺序，这是通过从所有堆栈的头部取出最小元素找到的。丹尼尔指出，我的排序将从最大到最小对我的堆栈进行排序（堆栈本身已经正确排序，最小的元素在顶部），这似乎是问题所在。

Answer 1

根据顺序，优先级队列中的第一个元素是具有最大值的元素，您是否对此感到困惑？该代码似乎期望第一个元素是具有最小值的元素。

Answer 2

回答发生了什么有点困难，因为您没有包含带有输入和输出的整个程序。我的猜测是，这是由于 2.8.1 中 PriorityQueue 的旧实现造成的。以下程序使用自定义排序，并用堆栈列表填充优先级队列：

import collection._                                                                                                 
import collection.mutable.PriorityQueue                                                                             
import collection.mutable.Stack                                                                                     



class Test[A](piles: Traversable[Stack[A]])(implicit ord: Ordering[A]) {                                            

  def PileOrdering = new Ordering[Stack[A]] {                                                                       
    def compare(a : Stack[A], b : Stack[A]) = ord.compare(a.head, b.head)                                           
  }                                                                                                                 

  // Use a priority queue, ordering on stack heads (smallest stack elems)                                           
  val pq = new PriorityQueue[Stack[A]]()(PileOrdering)                                                              

  // piles is a List[Stack[A]]                                                                                      
  pq ++= piles                                                                                                      

}                                                                                                                   

object Main {                                                                                                       
  def main(args: Array[String]) {                                                                                   
    val t = new Test(Seq(Stack(1, 2, 3), Stack(15, 8), Stack(3, 4, 9, 0, -1), Stack(45, 1, 2, 3, 4)))               
    while (t.pq.nonEmpty) {                                                                                         
      println(t.pq.dequeue)                                                                                         
    }                                                                                                               
  }                                                                                                                 
}  

程序输出：

Stack(45, 1, 2, 3, 4)                                                                                               
Stack(15, 8)                                                                                                        
Stack(3, 4, 9, 0, -1)                                                                                               
Stack(1, 2, 3)

with Scala trunk，这似乎是正确的。我应该指出 PriorityQueue 经历了一些更改，由于二进制兼容性原因，这些更改未包含在 2.8.1 中，但将在 2.9 中可用：

• 它曾经是一个序列，现在不再是序列 - apply 和 update 无法
• 通过调用 toString 来有意义地实现，或者迭代元素不会产生堆顺序 - 这是获取它的唯一方法是使用出队