Scala heap implementation

Question

I'm a Scala beginner, so it'd be great if anyone would be so kind to give some feedback.

package heap
import scala.collection.mutable.ListBuffer
class Heap[T](compareFunction: (T, T) => Int) {
private val HIGHER = 1
private val LOWER = -1
private val heapRepresentation = new ListBuffer[T]()
private def lastIndex = heapRepresentation.size - 1
private def valueOf(index: Int): T = heapRepresentation(index)
def add(item: T): Heap[T] = {
 heapRepresentation.append(item)
 bubbleUp(lastIndex)
 this
}
def swap(index1: Int, index2: Int) {
 val temp = valueOf(index1)
 heapRepresentation.update(index1, valueOf(index2))
 heapRepresentation.update(index2, temp)
}
def bubbleUp(currentIndex: Int) {
 def getParent(i: Int) = (i - 1) / 2
 if (currentIndex > 0) {
 val parentIndex = getParent(currentIndex)
 compareFunction(valueOf(currentIndex), valueOf(parentIndex)) match {
 case LOWER =>
 swap(currentIndex, parentIndex)
 bubbleUp(parentIndex)
 case _ =>
 }
 }
}
def bubbleDown(currentIndex: Int) {
 getLowerChild(currentIndex) match {
 case Some((lowerChildIndex, lowerChildValue)) =>
 if (compareFunction(valueOf(currentIndex), lowerChildValue) == HIGHER) {
 swap(currentIndex, lowerChildIndex)
 bubbleDown(lowerChildIndex)
 }
 case None =>
 }
}
def getLowerChild(index: Int): Option[(Int, T)] = {
 def getChildrenIndices(parentIndex: Int): (Int, Int) = (2 * parentIndex + 1, 2 * parentIndex + 2)
 val (leftChildIndex, rightChildIndex) = getChildrenIndices(index)
 val areChildrenInBoundsOfHeap = (rightChildIndex <= lastIndex) && (leftChildIndex <= lastIndex)
 if (!areChildrenInBoundsOfHeap) return None
 val (leftChildValue, rightChildValue) = (heapRepresentation(leftChildIndex), heapRepresentation(rightChildIndex))
 compareFunction(leftChildValue, rightChildValue) match {
 case LOWER => Some((leftChildIndex, leftChildValue))
 case _ => Some((rightChildIndex, rightChildValue))
 }
}
def pop: Option[T] = heapRepresentation.size match {
 case 0 => None
 case _ =>
 val firstValue = heapRepresentation(0)
 if (heapRepresentation.size == 1) {
 heapRepresentation.remove(0)
 return Some(firstValue)
 }
 swap(0, lastIndex)
 heapRepresentation.remove(lastIndex)
 bubbleDown(0)
 Some(firstValue)
}
override def toString = {
 s"[$heapRepresentation](${heapRepresentation.size})"
}
}

Usage of heap class

def compareInts(first: Int, second: Int): Int =
 if (first > second) 1
 else if (first == second) 0
 else -1
val heap = new Heap[Int](compareInts)
for (i <- 0 to 3) {
 heap.add((Math.random() * 100).toInt)
}
heap
heap.pop
heap.pop
heap.pop
heap.pop
def compareStrings(first: String, second: String): Int =
 if (first > second) 1
 else if (first == second) 0
 else -1
var heap2 = new Heap[String](compareStrings)
heap2.add("a")
heap2.add("cc")
heap2.add("")
heap2.pop
heap2.pop
heap2.pop
heap2.pop

Right now, I would like to get a Scala mindset, and get to know the tricks and tips. I have a background in PHP and JavaScript, and Scala is quite harder to learn, but way more elegant, so I want to master it!

• Alex L: Perhaps you could add some background to your script? What should it do? Are you looking for a focus on a specific part or concept?
• toto2: It would be more Scala-ish to build an immutable heap.
• toto2: Also, if you want some inspiration, you can look at scalaz Heap and the Scala PriorityQueue.

Answer 1

Writing utility classes is hard enough without reinventing everything from scratch each time. Whenever possible, class authors should take advantage of available tools. In this case, Scala has a trait for ordering objects in a collection: scala.math.Ordering and it should be used for the compareFunction which will undoubtedly require some adjustment of the code.

For the most part, the code is well laid out and easy to follow. Good job! Note that standard indentation for Scala code is two spaces. It's hard to tell if the four space indentation is what is used in the code, or if it was an artifact of transferring the code into this question.

While Scala pattern matching is a great tool, it is possible to over user it. I think that using it in the pop method is not just overkill, but also results in code that is harder to read. I would write it like this:

def pop: Option[T] = match {
 if (heapRepresentation.isEmpty) None
 else {
 val firstValue = heapRepresentation(0)
 if (heapRepresentation.size == 1) {
 heapRepresentation.remove(0)
 }
 else {
 swap(0, lastIndex)
 heapRepresentation.remove(lastIndex)
 bubbleDown(0)
 }
 Some(firstValue)
 }
}