■実装
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)となる
- 要素を頻繁に入れ替える
- 安定整列ではない