SkewHeap.scala

import Ordering.Implicits._

sealed abstract class SkewHeap[T] {
  def merge(that: SkewHeap[T])(implicit T: Ordering[T]): SkewHeap[T]
  def top: Option[T]
  def ++(that: SkewHeap[T])(implicit T: Ordering[T]): SkewHeap[T] = this merge that
  def +:(v: T)(implicit T: Ordering[T]): SkewHeap[T] = this merge SkewHeap(v)
  def :+(v: T)(implicit T: Ordering[T]): SkewHeap[T] = this merge SkewHeap(v)
  def size: Int
}

class Empty[T] extends SkewHeap[T] {
  def size: Int = 0
  def merge(that: SkewHeap[T])(implicit T: Ordering[T]): SkewHeap[T] = that
  def top: Option[T] = None
}

class Node[T](val key: T, val left: SkewHeap[T], val right: SkewHeap[T]) extends SkewHeap[T] {
  def merge(that: SkewHeap[T])(implicit T: Ordering[T]): SkewHeap[T] = {
    that match {
      case _: Empty[T] => {
        this
      }
      case that: Node[T] => {
        if (this.key > that.key) {
          new Node(this.key, this.right merge that, this.left)
        } else {
          new Node(that.key, that.right merge this, that.left)
        }
      }
    }
  }

  private val size_ = left.size + 1 + right.size

  def size: Int = size_

  def top: Option[T] = Some(key)
}

object Node {
  def unapply[T](that: Node[T]): Option[(T, SkewHeap[T], SkewHeap[T])] = {
    Some(that.key, that.left, that.right)
  }

  def apply[T](v: T): Node[T] = new Node(v, new Empty[T], new Empty[T])
}

object SkewHeap {
  def apply[T: Ordering](arg: T*): SkewHeap[T] = {
    arg.foldLeft[SkewHeap[T]](new Empty)(_ merge Node(_))
  }

  def unapply[T: Ordering](h: SkewHeap[T]): Option[(T, SkewHeap[T])] = {
    h match {
      case h: Node[T] => Some(h.key, h.left merge h.right)
      case _: Empty[T] => None
    }
  }
}

object Main {
  def main(arg: Array[String]): Unit = {
    def go[T: Ordering](h: SkewHeap[T]): Unit = if (h.size > 0) {
      val SkewHeap(v, rem) = h
      println(v)
      go(rem)
    }
    go(SkewHeap[Int](1, 2, 3, 4, 5, 6, 7, 8))
  }
}