ヒープソート

heapsort.scala

def hsort(list: Seq[Int]): Seq[Int] = {

  val l = new ArrayBuffer[Int]()

  // 3 1 2 -1 4 10 0
  // 3
  // 1 3 2
  // -1 3 2 1 4
  // -1 3 0 1 4 10 2
  def push(n: Int) {
    l.append(n)
    up(l.size - 1, n)
  }
  @tailrec
  def up(i: Int, n: Int) {
    if (i >= 0) {
      var pi = (i - 1) / 2
      val p = l(pi)
      if (n < p) {
        l.update(pi, n)
        l.update(i, p)
        up(pi, n)
      }
    }
  }

  // -1 3 0 1 4 10 2
  // ---
  // 2 3 0 1 4 10 : -1
  // 0 3 2
  // 0 1 2 3 4
  // 0 1 2 3 4 10
  // ---
  // 10 1 2 3 4 : 0
  // 1 10 2
  // 1 10 2 3 4
  // ---
  // 4 10 2 3 : 1
  // 2 10 4 3
  // ---
  // 3 10 4 : 2
  // ---
  // 4 10 : 3
  // ---
  // 10 : 4
  // ---
  // 10
  def pop(): Int = {
    val r = l(0)
    l.update(0, l.last)
    l.remove(l.size - 1)
    down()
    r
  }
  @tailrec
  def down(n: Int = 0) {
    if (n < l.size) {
      val r = l(n)
      val left = (2 * n) + 1
      val right = (2 * n) + 2
      val ll = if (left < l.size) l(left) else Int.MaxValue
      val rr = if (right < l.size) l(right) else Int.MaxValue
      r match {
        case _ if (r <= ll && r <= rr) => down(Int.MaxValue)
        case _ if ll < rr => {
          l.update(n, ll)
          l.update(left, r)
          down(left)
        }
        case _ if rr < ll => {
          l.update(n, rr)
          l.update(right, r)
          down(right)
        }
      }
    }
  }

  list.foreach(push)
  //println("heap = " + l)

  val sorted = list.map(_ => pop)
  ///println("sorted = " + sorted)

  sorted
}