在Scala中，制作最简单和最有效的小根堆的方法是什么？

Question

val maxHeap = scala.collection.mutable.PriorityQueue[Int] //Gives MaxHeap

使用Ordering将PriorityQueue转换为最小堆的最简洁有效方法是什么？

- user3335040

---

只是为了以后参考，很多时候“最简单”和“最高效”是互相排斥的。 - Jim Mischel

易于记忆：val minHeap = PriorityQueue[Int]()(Ordering[Int].reverse) - Sandeep

Answer 1

你需要定义自己的Ordering：

scala> object MinOrder extends Ordering[Int] {
         def compare(x:Int, y:Int) = y compare x
       }
defined object MinOrder

然后在创建堆时使用它：

scala> val minHeap = scala.collection.mutable.PriorityQueue.empty(MinOrder)
minHeap: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue()

scala> minHeap.ord
res1: Ordering[Int] = MinOrder$@158ac84e

- Marth

---

我认为你甚至不需要创建自己的Ordering，你可以使用已经存在的方法.reverse：Ordering [Int] .reverse。 - nachinius

完成（for completion）val minHeap = scala.collection.mutable.PriorityQueue.empty(Ordering[Int].reverse)翻译：创建一个反向排序的空可变优先队列minHeap。 - nachinius

Answer 2

2016年8月更新：您可以考虑由Chris Okasaki（chrisokasaki）提出的建议{{link1：chrisokasaki/scads/scala/heapTraits.scala}}。

该建议说明了Heap的“不太容易”的部分：

概念证明，具有合并操作的类型安全堆。这里，“类型安全”意味着接口永远不会允许在同一堆中混合不同的排序。特别是，

• 向现有堆添加元素时，插入不能涉及与用于创建现有堆的排序不同的排序；
• 当合并两个现有堆时，保证这些堆是使用相同排序创建的。

请参见{{link3：其设计}}。

val h1 = LeftistHeap.Min.empty[Int] // an empty min-heap of integers

- VonC