ヒープの並べ替えは、2つのプロセスに分割されます。
1.山を構築します。
ヒープは本質的に完全にバイナリツリーであり、次のことを満たす必要があります。ツリー内の非葉のノードのキーワードは、ノードのキーワード(またはある場合)のキーワードよりも大きくありません(またはそれ以上)。
ヒープは次のように分かれています。大きな根の山と小さな根の山。昇順は、大きなルートヒープを並べ替えるために使用され、下降順序は小さなルートヒープをソートするために使用されます。
大きなルートヒープの場合、最大の値を持つノードは、関数を調整することによりヒープルートに調整されます。
2。尾のヒープルートを保存し、残りのシーケンスの調整関数を呼び出します。調整が完了したら、テール-1(-1、-2、...、-I)の最大フォロワーを保存し、残りのシーケンスを調整し、ソートが完了するまでプロセスを繰り返します。
コードコピーは次のとおりです。
//関数を調整します
関数ヘッドジュスト(Elements、pos、len){
//現在のノード値を保存します
var swap = Elements [pos];
//現在のノードの左側に子ノードを見つけます
var child = pos * 2 + 1;
//子供がいなくなるまで再帰
while(child <len){
//現在のノードに右側にチャイルドノードがあり、右の子ノードが大きい場合は、右の子ノードを使用します
//現在のノードと比較します
if(child + 1 <len && elements [child] <elements [child + 1]){
子供 += 1;
}
//現在のノードを最大の子ノードと比較します。値が小さい場合は、値交換を実行し、交換後に現在のノードを見つけます
//子ノード上
if(elements [pos] <elements [child]){
Elements [pos] = Elements [child];
pos = child;
child = pos * 2 + 1;
}
それ以外{
壊す;
}
要素[pos] = swap;
}
}
//ヒープを構築します
function buildheap(elements){
//子ノードで最後のノードから開始し、ノードを子ノードと比較します。
//このノードで最大数を交換した後、同じ交換プロセスがフロントノードに順番に実行されます。
//大きなトップヒープが構築されるまで(昇順は大きなトップで、降順の順序は小さなトップです)
for(var i = elements.length/2; i> = 0; i-){
Headadjust(Elements、i、Elements.length);
}
}
関数ソート(要素){
//ヒープを構築します
BuildHeap(Elements);
//シーケンスの端から調整します
for(var i = elements.length-1; i> 0; i-){
//パイルの上部は常に最大の要素であるため、山の上部と尾要素が交換されます。
//最大要素が最後に保存され、後続の調整に参加しません
var swap = Elements [i];
要素[i] =要素[0];
要素[0] =スワップ;
//調整を行い、ヒープの上部に最大要素を調整します
Headadjust(Elements、0、i);
}
}
var Elements = [3、1、5、7、2、4、9、6、10、8];
console.log( '前:' +要素);
ソート(要素);
console.log( '後:' +要素);
効率:
時間の複雑さ:best:o(nlog2n)、最悪:o(nlog2n)、平均:o(nlog2n)。
空間の複雑さ:o(1)。
安定性:不安定