Какой самый простой и эффективный способ сделать кучу минут в 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: вы можете рассмотреть предложение chrisokasaki/scads/scala/heapTraits.scalaот Криса Окасаки ( chrisokasaki )

Это предложение иллюстрирует "не так просто" часть Heap:

Подтверждение концепции безопасных куч с помощью операции слияния.
Здесь "типовобезопасность" означает, что интерфейс никогда не позволит смешивать разные порядки в одной и той же куче.
Особенно,

• при добавлении элемента в существующую кучу эта вставка не может включать порядок, отличный от того, который использовался для создания существующей кучи, и
• при объединении двух существующих куч, кучи гарантированно создаются с одинаковым порядком.

Смотрите его дизайн.

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