在Scala中创建最小堆的最简单和最有效的方法是什么？
问题描述：
val maxHeap = scala.collection.mutable.PriorityQueue[Int] //Gives MaxHeap
使用Ordering将PriorityQueue转换为minHeap最简洁高效的方法是什么？在Scala中创建最小堆的最简单和最有效的方法是什么？
答
你必须定义自己的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] = [email protected]
答
更新2016年8月：你可以从考虑该建议chrisokasaki/scads/scala/heapTraits.scala。
该提案说明了Heap的“不那么容易”的一部分：
概念与合并操作类型安全堆的证明。
在这里，“类型安全”意味着界面绝不允许在同一个堆中混合不同的顺序。
特别地，
- 将一个元素增加到一个现有的堆时，该插入可以不涉及从用于创建现有堆的一个不同的排序，和
- 合并两个现有堆的情况下，堆是保证已经用相同的顺序创建。
请参阅its design。
val h1 = LeftistHeap.Min.empty[Int] // an empty min-heap of integers
仅供将来参考，通常“最简单”和“最有效”是相互排斥的。 – 2014-11-25 14:18:00