heapify関数の実装
heapify関数の実装
配列に対してインプレースでヒープを構築するheapifyを実装する
0-indexの場合は
子ノード
左 2n+1
右 2n+2
親ノードはfloor(n/2)で求まる
ヒープの種類
今回構築したのは最大ヒープなので、根が子よりも大きくなるべき
ノード番号が後ろの方、ボトムアップでより下の階層にある部分木から↑の関係を満たすように直していく この時、関係が崩れていれば要素をスワップする
さらにこの時、スワップした要素がさらにその下の子要素よりも小さい可能性があり、そのままではヒープが壊れてしまう。
再帰で波及させ、重い要素は適切な位置まで沈める
heapify(i)を実行する時点で、その子要素（childLeft, childRight）を根とする部分木は、すでにヒープ化が完了していなければならない
code:js
class HeapIterative extends Heap {
heapify(i) {
console.debug([HeapIterative.heapify()] first visit #${i}(${this.arr[i]}))
for (; ;) {
let largest = i;
largest = childLeft;
largest = childRight;
if (largest !== i) {
console.debug([HeapIterative.heapify()] swap #${i}(${this.arr[i]}) & #${largest}(${this.arr[largest]}))
i = largest
console.debug([HeapIterative.heapify()] next visit #${i}(${this.arr[i]}))
continue;
}
break
}
}
}
let arr = "7,3,2,6,5,8,1,4".split(",").map(e => +e);
const recHeap = new HeapRecursive(arr);
const recArr = recHeap.getHeap();
console.debug(max heap array: ${recArr.join(",")});
code:plain
visit #3(6) # 子より大きいのでヒープ条件を満たしている → swap不要 swap #2(2) & #5(8) # 子の方が大きいので swap。swap により #5 を根とする部分木のヒープ条件が壊れる可能性があるため、#5 部分木を再帰的にチェック visit #5(2) # #5 部分木はヒープ条件を満たしている → 終了 swap #1(3) & #3(6) # 子の方が大きいので swap。#3 部分木を再帰的にチェック swap #3(3) & #7(4) # 子の方が大きいので swap。#7 部分木を再帰的にチェック visit #7(3) # #7 部分木は葉なのでこれ以上下れない → 終了 swap #0(7) & #2(8) # rootより子が大きいので swap。#2 部分木を再帰的にチェック 非再帰版
code:js
class HeapIterative extends Heap {
heapify(i) {
for (; ;) {
let largest = i;
console.debug([HeapIterative.heapify()] heapify() with node #${i})
largest = childLeft < this.arr.length
? childLeft
: largest
;
largest = childRight < this.arr.length
? childRight
: largest
;
if (largest !== i) {
i = largest
continue;
}
break
}
}
}
let arr = "7,3,2,6,5,8,1,4".split(",").map(e => +e);
const itrHeap = new HeapIterative(arr);
const itrArr = itrHeap.getHeap();
console.debug(max heap array: ${itrArr.join(",")});