TopK.scala

class TopK {

   private val K = 10
   private val values = new Array[Long](K)
   private var size = 0

   def insert(item: Long) = {

      if (size < K) {
	values(size) = item
	swiftUp(size)
        size += 1
      }
      else if (item > values(0)) {
        values(0) = item
        heapify(0)
      }
   }

   def swiftUp(i: Integer) {       
        if (i != 0) {
           val parent = getParent(i)
   	   if (values(parent) > values(i)) {
	      exchange(parent, i)
              swiftUp(parent)
	   }
        }
   }

   def getParent(i: Integer): Integer = {
      if (i % 2 == 0) {
	return i / 2 - 1
      }
      else {
        return i / 2
      }
   }

   def get(): Array[Long] = {
      values.take(size).sortBy(_ * -1L)
   }

   override def toString = java.util.Arrays.toString(values)

   private def exchange(i: Integer, j: Integer) {
      val temp = values(i)
      values(i) = values(j)
      values(j) = temp
   }

   private def heapify(i: Integer) {      

       val left = 2*i + 1 
       val right = 2*i + 2
       var smallest = i

       if (left < K && values(smallest) > values(left)) {
	 smallest = left
       }

       if (right < K && values(smallest) > values(right)) {
	 smallest = right
       }

       if (i != smallest) {
	  exchange(i, smallest)
          heapify(smallest)
       }
   }
}