[アルゴリズム]優先キュー-ヒップ


アレイ別優先キューの非効率性(heap)による優先キューの実現

  • ヒップホップ(Heap)は資料構造である.この場合、優先キューはデータ構造ではなく、優先度別にデータを取り出すための機能的定義であると考えられる.
  • ヒップホップ特性:
  • 親要素が子要素以下である必要があります.
  • 完全バイナリツリーで、高さ0から左から順に資料を記入します.したがって、右側のサブノードがある場合、左側のサブノードは存在しません.
  • **サブノードが2つしかない「バイナリ・ツリー」に、データを完全バイナリ・ツリーにするための属性を左から右に追加します.
  • 親ほど優先順位が高い.したがって、popはルート要素をポップアップします.
  • 臀部の高さは0からの観点でlog 2 N(底部は2)である.ここでNはノード全体の個数である.すなわち,ノード全体の個数が8であれば,このhipは高さ3を有する完全なバイナリツリーとなる.例えば、以下のバイナリツリーは、高さ2のバイナリツリー(0から)と呼ぶことができる.

  • ソース:ブログリンク
  • hipの「挿入」にはlognの時間的複雑さが必要です.なぜなら、挿入時に完全バイナリツリーのプロパティで左から右に順番に表示されると、最後の空白部分から塗りつぶしが開始されます.たとえば、上図では6の右側のサブエレメントで塗りつぶされます.ただし、パディング数が2の場合、hipの特性上、親要素は子要素より小さくなければならないため、パディング数が親要素より小さい場合は交換する必要があります(この場合、左側の子ノードは親要素より小さいと判断しているので、新しく追加した要素と比較する必要はありません).
  • そのように交換されたら?もう一度、親要素と比較します.このようにして、最終的にはルート要素を比較するが、実施回数が最悪の場合は高度に達するため、lognの時間的複雑さがある.
  • 挿入に続いて、削除もlognの時間的複雑さを有する.hipの削除は、まずルートノードから削除されます.この場合、削除され、終了ではなくhipのプロパティに基づいて並べ替える必要があります.その前に、先端要素をルートノードに配置し、下部要素が新しく変更されたルートノードと比較されるまで並べ替えます.そのため、最終的には高さと同じ時間複雑さが必要になります.
  • top()メソッドは、クエリーが非常に容易です.ルートノードを出力するだけです.
  • 特性に応じて実装される「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)の差が非常に大きい…).