[Scala][基礎アルゴリズム] 選択ソート（２） ヒープソート

『データ構造』P116　より、
ヒープとは、「任意の節についてその節のキー値がその子のキー値以上であるような完全二分木」のこと。
ヒープ整列法は、「与えられた配列をヒープに仕立てる前半と、最大キーを選択しては配列の後尾に移動させる操作を繰り返す後半とからなる。」
・計算量はO(nlogn)

Wikipediaの説明：ヒープソート

object HeapSort {
    def sort(array: Array[Int]) {
        // 初期ヒープ作成
        def makeInitialHeap() {
            val nodeIdx = array.length / 2 - 1 // 末端の二分木ノード
            for(i <- nodeIdx to 0 by -1) sift(i, array.length-1)
        }
        // コアとなるふるい操作を行う関数
        // nodeIdx番目の要素をヒープ中の適切な位置に移動する
        def sift(nodeIdx: Int, stop: Int) {
            if(2 * nodeIdx <= stop) {
                val j = maxChildIdx(nodeIdx, stop)
                if (array(nodeIdx) < array(j)) {
                    swap(nodeIdx, j)
                    sift(j, stop)
                }
            }
        }
        // nodeIdx番目の要素の子要素のうち、大きいほうのインデックスを返す
        def maxChildIdx(nodeIdx: Int, stop: Int): Int = {
            val j = 2 * nodeIdx
            if (j == stop || array(j) >= array(j+1)) j else j + 1
        }
        // swap関数
        def swap(x: Int, y: Int) {
            val tmp = array(x); array(x) = array(y); array(y) = tmp;
        }

        makeInitialHeap() // 初期ヒープ作成
        for(last <- array.length-1 until 0 by -1) {
            swap(0, last) // ルート要素を末尾に移動
            sift(0, last - 1) // 新しいルート要素をふるいにかける
        }
    }

    // main
    def main(args: Array[String]) {
        val array = Array(2,9,3,5,8,7,4,1,6)
        println("ソート前: " + array.toString)
        sort(array)
        println("ソート後: " + array.toString)
    }
}

// 実行結果

ソート前: Array(2, 9, 3, 5, 8, 7, 4, 1, 6)
ソート後: Array(1, 2, 3, 4, 5, 6, 7, 8, 9)