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?

Just for future reference, very often "easiest" and "most efficient" are mutually exclusive. — Jim Mischel, Nov 25 '14 at 14:18
Easy to remember: `val minHeap = PriorityQueue[Int]()(Ordering[Int].reverse)` — Sandeep, Aug 22 '20 at 07:37

Marth · Accepted Answer · 2016-07-15T07:06:40.653

19

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

edited Jul 15 '16 at 07:06

answered Nov 25 '14 at 06:22

Marth

23,920
3
60
72

12

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 – nachinius Oct 30 '16 at 23:54
11

for completion val minHeap = scala.collection.mutable.PriorityQueue.empty(Ordering[Int].reverse) https://codebunk.com/pb/788100787 – nachinius Oct 31 '16 at 00:01

score 2 · Answer 2 · answered Aug 14 '16 at 02:24

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

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

2 Answers2