JavaScriptは積み上げ順序を実現します.
5797 ワード
JSは積み上げ順序を実現します
考え方
まず山は二叉の木で、一番山と一番小さい山に分けられます.最大ヒープは、各親ノードがサブノードより大きいことを表し、最小スタックが反対である.並べ替えの中で山は完全に二叉の木です.いくつかの公式に関連しています.
いくつかの公式
つの二叉の木は完全に二叉の木です.彼のノードの計算式はparent(i)=flor(i/2)です.ileft(i)=2 iiright(i)=2 i+1配列中の数式には変化があるparent(i)=flor(i-1)/2)があります.ileft(i)=2 i+1iright(i)=2(i+1);
主要な考え方
まず一番大きな山の調整をして、一番大きな山の頂部、つまり一番大きい数を最後まで運んでください.その後、ヒープのサイズを1縮小し、その後も最大ヒープ調整を続けて上記のステップを繰り返します.
最大の実現
下のコードが一番多く実装されていることに注意してください.最後のノードの親ノードから各ツリーを調整し始めます.
コードの実装
考え方
まず山は二叉の木で、一番山と一番小さい山に分けられます.最大ヒープは、各親ノードがサブノードより大きいことを表し、最小スタックが反対である.並べ替えの中で山は完全に二叉の木です.いくつかの公式に関連しています.
いくつかの公式
つの二叉の木は完全に二叉の木です.彼のノードの計算式はparent(i)=flor(i/2)です.ileft(i)=2 iiright(i)=2 i+1配列中の数式には変化があるparent(i)=flor(i-1)/2)があります.ileft(i)=2 i+1iright(i)=2(i+1);
主要な考え方
まず一番大きな山の調整をして、一番大きな山の頂部、つまり一番大きい数を最後まで運んでください.その後、ヒープのサイズを1縮小し、その後も最大ヒープ調整を続けて上記のステップを繰り返します.
最大の実現
下のコードが一番多く実装されていることに注意してください.最後のノードの親ノードから各ツリーを調整し始めます.
コードの実装
//
//
//
//
//
//parent(i) = floor(i/2);
//ileft(i)=2i;
//iright(i)=2i+1;
//
//parent(i) = floor((i-1)/2);
//ileft(i)=2i+1;
//iright(i)=2(i+1);
//
//
//
function getMaxHeap(array,i,heapSize) {
var imax,ileft,iright;
while (true) {
imax=i;
ileft=2*i+1;
iright=2*(i+1);
if (iLeftarray[i]<array[ileft]){
imax=ileft;
}
if (irightarray[i]<array[right]){
imax=iright;
}
}
}
/**
* index
* @array
* @index
* @heapSize
**/
function maxHeapify(array, index, heapSize) {
var iMax, iLeft, iRight;
while (true) {
iMax = index;
iLeft = 2 * index + 1;
iRight = 2 * (index + 1);
if (iLeft < heapSize && array[index] < array[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && array[iMax] < array[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
index = iMax;
} else {
break;
}
}
return array;
}
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
function buildMaxHeap(array, heapSize) {
var i,iParent = Math.floor((heapSize - 1) / 2);//
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, heapSize);
}
return array;
}
function heap_sort(arr) {
buildMaxHeap(arr,arr.length);
for (let i = arr.length-1; i >0; i--) {
swap(arr,0,i);
buildMaxHeap(arr,i);
}
return arr;
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(heap_sort(elements));