function heap_sort(numbers,array_size)
{
    var temp;

    //ヒープ構築
    //二分木なので親ノードのインデックス
    //(n-1)/2
    for(var i=parseInt((array_size-1)/2);i >= 0;i--)
    {
        max_heap(numbers,i,array_size-1);
    }

    //ヒープソート実行
    //値を昇順に並べる。
    
    //先頭要素(最大値)を配列の最後に移動
    //最後の要素を無視してヒープを構築
    //配列内で最も小さな値から順に並ぶ
    for(var i=array_size-1;i > 0;i--)
    {
        temp = numbers[0];
        numbers[0] = numbers[i];
        numbers[i] = temp;
        max_heap(numbers,0,i-1);
    }

}

//Max-heap を構築

//親ノードは子ノードより大きいか等しい
//@param numbers ソートしたい配列
//@param root 親ノードとなる要素のインデックス
//@param bottom 最後の要素のインデックス
function max_heap(numbers,root,bottom)
{
    //子ノードのインデックス
    var child = (2*root)+1;

    //親ノードの値を保持
    var temp = numbers[root];

    while(child <= bottom) 
    {
        if(child < bottom && numbers[child+1] > numbers[child]) 
        {
            //二分木のふたつの子ノードから値が大きい子ノードを選択
            child = child + 1;
        }
        if(temp > numbers[child])
        {
            //親ノードの値が子ノードの値より大きい場合何もしない
            break;
        } 
        else if(temp <= numbers[child]) 
        {
            //親が子より小さいか等しいとき
            //親と子を入れ替える
            numbers[parseInt((child-1)/2)] = numbers[child];
            //子ノードのインデックスを進める
            child = (2*child)+1;
        }
    }
    //親ノードとなる要素に値を入れる
    numbers[parseInt((child-1)/2)] = temp;
}

//Max-heap を構築する。再帰を利用。


function max_heap_recursive(numbers,root,bottom)
{
    //子ノードのインデックス
    //配列の先頭要素のインデックスが 0
    //子ノードは 2n+1 と 2n+2 で計算する
    var l_idx = (root*2)+1;
    var r_idx = (root*2)+2; 

    //最大値を持つ要素のインデックス
    var maxChild;

    if(l_idx <= bottom && numbers[l_idx] > numbers[root]) 
    {
        maxChild = l_idx;
    } 
    else 
    {
        maxChild = root;
    }

    if(r_idx <= bottom && numbers[r_idx] > numbers[maxChild]) 
    {
        maxChild = r_idx;
    }

    if(maxChild != root) 
    {
            var temp = numbers[root];
            numbers[root] = numbers[maxChild];
            numbers[maxChild] = temp;
            //配列の先頭要素には最大値を持つ要素のインデックスを指定
            max_heap_recursive(numbers,maxChild,bottom);
    }
}

//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前：");
for(var i=0; i < h.length;i++)
{
    document.write(h[i]+" ");
}
document.write("<br>");

//ヒープソート
heap_sort(h,h.length);

document.write("整列後：");
for(var i=0; i < h.length;i++)
{
    document.write(h[i]+" ");
}

整列前：6 3 8 4 5 1 2 9 7 0
整列後：0 1 2 3 4 5 6 7 8 9