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

Question

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

使用 Ordering 将 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 月更新：您可以考虑Chris Okasaki ( )的建议chrisokasaki/scads/scala/heapTraits.scala。chrisokasaki

该提案说明了一个“不那么容易”的部分Heap：

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

• 将元素添加到现有堆时，该插入不能涉及与用于创建现有堆的顺序不同的顺序，并且
• 合并两个现有堆时，保证创建的堆具有相同的顺序。

看它的设计。

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