What is the easiest and most efficient way to make a min heap in Scala?

Question

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

What is the most concise and efficient way to use Ordering to turn a PriorityQueue into a minHeap?

Answer 1

You'll have to define your own Ordering :

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

Then use that when creating the heap :

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

Update August 2016: you can consider the proposal chrisokasaki/scads/scala/heapTraits.scala from Chris Okasaki (chrisokasaki).

That proposal illustrates the "not-so-easy" part of an Heap:

Proof of concept for typesafe heaps with a merge operation.
Here, "typesafe" means that the interface will never allow different orderings to be mixed within the same heap.
In particular,

• when adding an element to an existing heap, that insertion cannot involve an ordering different from the one used to create the existing heap, and
• when merging two existing heaps, the heaps are guaranteed to have been created with the same ordering.

See its design.

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