在Scala中创建最小堆的最简单和最有效的方法是什么？

Question

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

使用排序将PriorityQueue转换为minHeap的最简洁、最有效的方法是什么？

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

Answer 2

2016年8月更新:您可以考虑chrisokasaki/scads/scala/heapTraits.scala来自)的建议。

这个提议说明了Heap的“不那么容易”的部分。

类型库与合并操作的概念证明。 在这里，"typesafe“意味着接口将永远不允许在同一个堆中混合不同的顺序。 特别地，

• 当向现有堆添加元素时，该插入不能涉及与创建现有堆的顺序不同的顺序，以及
• 当合并两个现有堆时，可以保证以相同的顺序创建堆。

见它的设计。

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