[アルゴリズム]優先キュー-ヒップ
アレイ別優先キューの非効率性(heap)による優先キューの実現
ソース:ブログリンク
特性に応じて実装される「heap」-push,pop,top
Popメソッド(pushよりも複雑な論理が必要)
> const pop = () => {
[heap[1],heap[heap.length-1]] = [heap[heap.length-1],heap[1]]
heap.pop();
let idx = 1;
let left = undefined;
let right = undefined;
let std = undefined;
let height = Math.floor(Math.log2(heap.length-1));
let cnt = 0;
while (true) {
cnt += 1
std = heap[idx];
idx *= 2;
left = heap[idx];
right = heap[idx+1];
if (left && right) {
if (left < right && std > left) {
[heap[idx/2],heap[idx]] = [heap[idx],heap[idx/2]];
} else if (right<=left && std>right) {
[heap[idx/2],heap[idx+1]] = [heap[idx+1],heap[idx/2]];
} else {
break;
}
} else if (left && !right) {
if (std>left) {
[heap[idx/2],heap[idx]] = [heap[idx],heap[idx/2]];
} else {
break;
}
} else {
break;
}
idx += 1;
if (cnt === height) {
break;
}
}
}
非常に簡単なtop方法
上記の実装で特に注意すべき点は、heapの作成時に配列が使用されているが、配列のインデックスの0は空であることである.これはhipの特性に関係しており,ノードの個数が2の倍数単位に増加するたびに,高さ毎に1格+を増加させる手法を用いてpopやpushの場合,直系親または直系子のインデックスを容易に求めるために2(親要素),2を乗じた(子要素)部分に分ける.
例えば、[2,3,5,4,6,7]
2
3 5
4 6 7
上のようなお尻があると言うと、
配列内のhipのインデックス0を0に残すと、
[0.2.3.5.4.6.7]
たとえば、インデックス7に新しい要素、たとえば8を追加する場合は、8が親要素より小さいかどうかを比較する必要があります.
親要素のインデックスをコードで取得できる必要があります(毎回ナビゲートできません...).この方法で、新しく追加された要素のインデックス(この場合は7)に2を割り当てると、7/2=3=>インデックス3の値は5であり、8が一番下の7つの右ノードに入ると、正確には彼の親要素は5である.ただし、インデックス0を0にクリアしないと、この計算は実行できません.逆にpopはサブエレメントと比較する必要があります.この場合、親エレメントのインデックスに2(左側のサブノードのインデックス)を乗じ、2を乗じて1(右側のサブノードのインデックス)を加えると、必要な値が得られます.
実は...以前に並べられた優先キューとfor文で100000回のpushとpop(同じ条件)を実行して比較すると,実際にかかった時間自体にも明らかな差がある(時間複雑度O(N)とO(logn)の差が非常に大きい…).
Reference
この問題について([アルゴリズム]優先キュー-ヒップ), 我々は、より多くの情報をここで見つけました https://velog.io/@0715yk/Algorithm-우선순위-큐-힙-m2irkmr8テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol