Heapとは?

1792 ワード
テキストリンク
hipは完全バイナリツリー(最後のレベルを除くすべてのレベルノードが埋め込まれたツリー)であり、ルートが最大値であるか最小値であるかによって、最大と最小のhipがある.

Bは完全にバイナリツリーではない.
最大臀部の親ノードは子ノードの値より大きく、最小臀部の親ノードは子ノードの値より小さい.これは、最大最小値を探すのに役立ちます.

最大ヒップ


最大ヒップで、ルートノードの値が最大です.また,N個の完全バイナリツリーが含まれている場合,ツリーの高さはlognである.

最大臀部を挿入

  • の最後の位置に挿入可能な数を配置します.
    完全バイナリツリーなので、一番左の位置が最後の位置になります.
  • の親ノードと比較して、現在のノードが大きい場合は位置が変更されます.
  • の親に比べて、現在のノードが小さい場合は停止します.この位置が挿入位置となる.
  • の最大高さに移動するので、複雑度はO(logn)O(logn)O(logn)である.

    • 最大ヒップの除去(Remove Maxヒップ)


    削除するノード
  • をルートノードツリーの最後の位置を削除するノードの位置に移動します.(ターゲットが削除されました)
  • 本から、子供と比較して、子供がもっと大きくなれば、位置を変えて繰り返します.
  • 子供が小さいかいないかで、止まります.
  • の最大高さに移動するので、複雑度はO(logn)O(logn)O(logn)である.

    • 最小ヒップ


    ルートノードは、ツリーの最小値の構造です.

    最小ヒップ数を挿入


    最大ヒップと不等号を逆挿入するだけで実現できます.

    最小ヒップの削除


    最大臀部削除と不等号を逆方向に実行するだけで実現できます.

    JAVAのお尻


    JAVAでは優先順位順のPriorityQueue内部にHeapを採用しており、デフォルトでは最小値は優先順位の高い最小お尻である.最大お尻に変えたいなら
  • Comparatorまたは
    • PriorityQueue<Integer> q = new PriorityQueue<>(1, 비교자)
    -1に
  • の値自体を乗じる方法
    • 全部で2種類あります.
    mod_proxy parameter
    Liunxシステムプログラミングにおけるopen(),close(),lseek(),write(),read()および関連例