Standard Binary Heap in a Functional Setting

Heap.scala

/**
 * A standard binary min-heap based on http://arxiv.org/pdf/1312.4666v1.pdf
 */
sealed trait Heap[+A] {
  def min: A

  def left: Heap[A]
  def right: Heap[A]
  def isEmpty: Boolean

  // Both 'size' and 'height' are stored in each node.
  val size: Int
  val height: Int

  /**
   * Inserts the given element `x` into this heap.
   *
   * Time - O(log n)
   * Space - O(log n)
   */
  def insert[B >: A : Ordering](x: B): Heap[B] =
    if (isEmpty) Branch(x)
    else if (left.size == math.pow(2, left.height) - 1 && right.height < left.height) 
      bubbleUp(min, left, right.insert(x))
    else bubbleUp(min, left.insert(x), right)

  /**
   * Bubbles the given context (`x`, `l` and `u`) up to the heap and fixes violations
   * of min-heap invariant.
   *
   * Time - O(log n)
   * Space - O(log n)
   */
  def bubbleUp[B : Ordering](x: B, l: Heap[B], r: Heap[B]): Heap[B] = {
    val ordering = Ordering[B]; import ordering._

    (l, r) match {
      case (Branch(y, lt, rt), _) if (x > y) => 
        Branch(y, Branch(x, lt, rt), r)
      case (_, Branch(z, lt, rt)) if (x > z) => 
        Branch(z, l, Branch(x, lt, rt))
      case (_, _) => 
        Branch(x, l, r)
     }
   }
}

case object Leaf extends Heap[Nothing] {
  def min: Nothing = throw new NoSuchElementException("An empty heap.")
  def left: Heap[Nothing] = throw new NoSuchElementException("An empty heap.")
  def right: Heap[Nothing] = throw new NoSuchElementException("An empty heap.")
  val size: Int = 0
  val height: Int = 0
  def isEmpty: Boolean = true
}

case class Branch[+A](min: A, left: Heap[A] = Leaf, right: Heap[A] = Leaf) extends Heap[A] {
  def isEmpty: Boolean = false
  val size: Int = left.size + right.size + 1
  val height: Int = math.max(left.height, right.height) + 1
}