class Heap[Item <% Ordered[Item] : Manifest](maxSize: Int, less: (Item,Item) => Boolean) {

  var size: Int = 0

  val arr = new Array[Item](maxSize)

  def insert(newItem: Item): Unit = {
    arr(size) = newItem
    fixInsertion(size)
    size += 1
    //println(arr.dropRight(arr.length - size).mkString(","))
  }

  def += (newItem: Item): Unit = {
    insert(newItem)
  }


  def top(remove: Boolean = true): Item =  {
    if(!remove)
      return arr(0)
    swap(0, size-1)
    size -= 1
    fixRemoval(0)
    //println(arr.dropRight(arr.length - size).mkString(","))
    arr(size)
  }

  def remove(item: Item, i: Int = 0): Unit = {
    if (i < size)
      if (arr(i).equals(item)) {
        size -= 1
        swap(i, size)
        fixRemoval(i)
      }
      else
        remove(item, i+1)

  }

  def isEmpty: Boolean =  {
    size == 0
  }

  private def fixInsertion(i: Int): Unit = {
    if (i > 0 && less(arr(i),arr(i/2))) {
      swap(i, i/2)
      fixInsertion(i/2)
    }
  }

  private def fixRemoval(i: Int): Unit = {
    val j = i+1
    if (j * 2 <= size) {
        val next = if (j*2 < size) { if (less(arr(j*2-1), arr(j*2))) j*2-1 else j*2} else j*2-1
        if (less(arr(next), arr(i))) {
            swap(i, next)
            fixRemoval(next)
        }
    }
  }

  private def swap(a: Int, b: Int): Unit = {
     val swap = arr(b)
    arr(b) = arr(a)
    arr(a) = swap
  }


}