@blog.justoneplanet.info

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * swap
 * @param {array} ary
 * @param {int} x
 * @param {int} y
 */
var swap = function(ary, x, y){
    console.log(ary.toString());
    var a = ary[x];
    var b = ary[y];
    ary[x] = b;
    ary[y] = a;
    console.log(ary.toString());
    console.log('---');
    return true;
}

/**
 * heapify
 * 3要素を比較し最も大きい要素を親とする
 * @param {array} ary
 * @param {int} i
 * @param {max} max
 */
var heapify = function(ary, i, max){
    var l = 2 * i + 1;
    var r = 2 * i + 2;
    var li = 0;
    if(l < max && ary[l] > ary[i]){
        li = l;
    }
    else{
        li = i;
    }
    if(r < max && ary[r] > ary[li]){
        li = r;
    }
    if(li !== i){
        swap(ary, i, li);// 比較した3要素の最大値を親に移動…(a)
        heapify(ary, li, max);
        /*(a)によりiの子孫（孫以下）のノードでヒープが崩れた可能性がある*/
        /*従って、aryのヒープ特性を保持するため、leaf方向に向けて再帰でheapify*/
    }
}

/**
 * buildHeap
 * 子を持つ要素のうち最も大きいインデックスを持つ要素より前をheapifyする
 * @param {array} ary
 */
var buildHeap = function(ary){
    for(var i = Math.floor(ary.length / 2) - 1; i >= 0; i--){
        heapify(ary, i, n);
    }
}

/**
 * hsort
 * @param {array} ary
 */
var hsort = function(ary){
    buildHeap(ary);// 初期のヒープ構造を生成
    for(var i = ary.length - 1; i > 0; i--){
        swap(ary, 0, i);// 先頭の最大値と最後尾の要素をswap
        heapify(ary, 0, i);// 最後尾の要素を除いてヒープ構造を再構築
    }
}


hsort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

• データの出現順序による計算量の変化が小さく、計算量はO(n log n)となる
• 要素を頻繁に入れ替える
• 安定整列ではない