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?

Ul

Just for future reference, very often "easiest" and "most efficient" are mutually exclusive. – Rainier

Easy to remember: val minHeap = PriorityQueue[Int]()(Ordering[Int].reverse) – Stenograph

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

Coadjutress

I think you don't even need to create your own Ordering, you can use method .reverse of an already existing one: Ordering[Int].reverse – Sunbow

for completion val minHeap = scala.collection.mutable.PriorityQueue.empty(Ordering[Int].reverse) codebunk.com/pb/788100787 – Sunbow

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

Winna