scala版堆实现的堆排序和优先级队列

HeapSort.scala

package data

import java.util.Date

object HeapSort {
	
  class MaxHeap[T <% Ordered[T] : ClassManifest](val initialSize: Int) {
    private var underlying: Array[T] = new Array[T](initialSize + 1);

    private var size = 0

    private def checkSize() {
      if (size + 1 == underlying.length)
        underlying = growArray(underlying)
    }

    /**
     * 向堆中添加元素
     */
    def add(item: T) {
      checkSize()
      size += 1
      underlying(size) = item
      fixUp(size)
    }

    def head = underlying(1)

    /**
     * 移除堆顶部的元素，并且返回
     */
    def pop = {
      val head = underlying(1)
      underlying(1) = underlying(size)
      underlying(size) = null.asInstanceOf[T]
      size -= 1
      fixDown(1)
      head
    }

    /**
     * 从某个叶子节点开始往上重新调整结构，保证堆的性质。
     *
     * @param size 从size位置开始向上调整
     */
    def fixUp(position: Int): Unit = {
      var k = position
      while (k > 1) {
        val j = k >> 1
        if (underlying(j) > underlying(k))
          return;

        swap(k, j);
        k = j
      }
    }

    /**
     * 从上往下调整结构，保证堆的性质。
     */
    def fixDown(position: Int) {
      def le(pos1: Int, pos2: Int): Boolean = {
        underlying(pos1) <= underlying(pos2)
      }

      def gt(pos1: Int, pos2: Int): Boolean = {
        underlying(pos1) > underlying(pos2)
      }

      var current = position
      var i = 0;
      while ({i = current << 1; i} <= size && i > 0) {
        if ((i < size) && le(i, i + 1))
          i += 1;
        if (gt(current, i))
          return

        swap(current, i)
        current = i
      }
    }

    /**
     * 重建堆
     */
    def heapify() {
      for (i <- (1.to(size / 2)) reverse)
        fixDown(i);
    }

    /**
     * 堆排序
     */
    def sort(): Array[T] = {
      val oldSize = size
      for (i <- (2 to size) reverse) {
        swap(1, i)
        size -= 1
        heapify()
      }
      size = oldSize
      underlying
    }

    @inline
    def swap(i: Int, j: Int) {
      val temp = underlying(i)
      underlying(i) = underlying(j)
      underlying(j) = temp
    }

    /**
     * 测试使用
     */
    def snapshot() =
      (0 to size) zip underlying foreach {
        e =>
          Console.printf ("%d\t%s\n" ,e._1, e._2)
      }

  }

  def growArray[T: ClassManifest](source: Array[T]) = {
    val y = new Array[T](source.length * 2)
    Array.copy(source, 0, y, 0, source.length)
    y
  }

  class Task(val nextExecutionTime: Long) extends Ordered[Task] {
    override def compare(that: Task): Int = {
      (this.nextExecutionTime - that.nextExecutionTime).asInstanceOf[Int]
    }

    override def toString(): String = {
      "Task[%s]".format(new Date(nextExecutionTime))
    }

  }

  def main(args: Array[String]): Unit = {

    val taskQueue = new MaxHeap[Task](10)

    for (i <- 1 to 10)
      taskQueue add new Task(new Date().getTime + i * 10000)

    Console println taskQueue.head
    taskQueue.snapshot()

    val start = System.nanoTime

    taskQueue.sort()
    taskQueue.snapshot()

    Console println (System.nanoTime - start) / 1000.0 / 1000 / 1000

  }

}