ヒープ - Min e Max

ヒープ - 最小ヒープ

ヒープは、優先順位リストのより効率的なバージョンです。プライオリティ キューのソート済みおよびアンソートの挿入および削除方法を考慮します。アンソートでは挿入コスト O(1)、削除コスト O(n) がかかりますが、ソート済みの挿入コストは O(n)、削除コスト O(1) です。

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

ヒープは配列によって構築されますが、その表現はバイナリ ツリーであり、最も優先度の高い要素が最上位のルートになります。上から下、右から左まで満たされており、欠けている子はありません!

?

ただし、最も高いキー値によって定義される最も高い優先順位を持つデータ構造が構築される可能性があります。この場合、最大ヒープが得られます。これについては後で説明します。

最小ヒープ

有効なヒープであるためには、すべての子要素の優先順位が親要素よりも低いか同じである必要があります。さらに、欠落した子がなく完全である必要があります。そうでない場合、配列には空白スペースが生じます。

?

この定義をより正式に実行する方法は、レベル 0、1、2、... h − 1 に可能な最大の要素があり、レベル h に存在する要素が割り当てられている場合にバイナリ ツリーが完成すると言うことです。できるだけ左に。

前述したように、ヒープは配列 (緑色で表示) で構成されていますが、以下の画像に示すようにツリー構造として見ることができます。

ヒープをアセンブルするには、最初の要素を位置 0 に配置する方法と、位置 0 を使用しない方法の 2 つがあります。この記事では、2 つの場合の違いについて説明します。上部の要素には常にその子があり、一般に下部の要素として知られています。これらの子を検出するには、インデックス 0 の場合、次の計算を使用してこの情報を取得できます。

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

0 が入力されていないバージョンを使用する場合は、合計を減らすだけです。つまり、1-1=0、親の場合はインデックス / 2 です。

入れる

これは常に最後に追加されます。唯一の懸念は、子要素が親よりも低いキーを持っているかどうかを確認するときです。このために、挿入された要素のキーが更新されるときにバブリングアップが実行されます。必要に応じて変化する父親と比較してください。

より詳しく言うと、要素をツリーの最後の空きスペースに配置し、そのキーと親のキーを比較する必要があるため、そのキーにアクセスするために親のインデックスを計算する必要があります。父親を調べるには、次の計算を使用します。

parent = (indexDoFilho -1)/2

そして、この場合、indexDoFilho が欠落しています。これを取得するには、変数を現在のインデックスとして取ります。最後に追加である挿入を行っているため、現在のインデックスは最後のもので、次のようになります。

currentIndex = size-1

現在のインデックスが得られたので、Parent を呼び出し、挿入される要素の父親が誰であるかを確認します。この新しい要素の親が必要なのは、ツリーを正しく構成するには、この要素をその親と比較する必要があり、そのキーが小さい場合は位置を交換する必要があるためです。

現在のインデックスが 0 より大きく (使用できないインデックスの選択を避けるため)、現在のインデックスが親のインデックスより小さい限り、この条件が true の場合、要素は親と交換する必要があります。最小ヒープの所有権を保証するため、スワップが発生し、現在のインデックスが親のインデックスを受け取り、親の親 (KKKKK) を に取得します。スワップは、通常の価値交換の仕組みを利用した手法です。

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

関連性があること:

parent = (indexDoFilho -1)/2

スワップは値を交換する通常の方法です:

currentIndex = size-1

現在の (子) 要素の値が親の値より小さい場合、これは最小ヒープ プロパティに違反していることを示します。最小ヒープでは、親は常に子以下でなければなりません。 この条件が満たされない場合、子は親と場所を交換する必要があります。これにより、プロパティが維持される正しい位置が見つかるまで、小さい値がヒープ内で「登り」続けます。

>

取り除く

インデックス 0 の要素を削除しますが、ツリーは完成しません。これを解決するには、配列の最後の要素を先頭にプルします。つまり、追加された最後の要素がツリーの先頭に移動します。その後、もう一度確認しますが、今度は上から下まで確認します。つまり、今こそ親と子を比較する時期なのです！ (沈下)
SinkDown() メソッドは、要素が正しい位置に配置されるまで、要素をヒープ内で下に移動します (または「シンク」します)。要素の値はその子の値以下になります (子のある位置にある場合)。 .
SinkDown には、ルートから始まる最小キーを持つ要素のインデックスを格納する変数と、現在のインデックス用の変数があります。次に、現在の要素のインデックスが最も低いキーを持つ要素のインデックスと等しくなるまでループが続きます。ループ内で、現在の子の子を取得し、子が配列範囲内にあるかどうかを確認します。子のインデックスが最小インデックスより小さい場合は、最小値を更新します。

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

この場合:

protected int parent(int index){
        return (index-1)/2;
}

まとめ：

最小ヒーププロパティ:

• 完全なバイナリ ツリー構造。
• 親ノードは常にその子ノード以下の値を持ちます。
• 配列を介して実装され、子と親の位置はインデックスに基づく数式によって決定されます。

子と親の位置を計算するには:

• 左: leftChild = インデックス * 2 1
• 右: rightChild = インデックス * 2 2
• 親: 親 = (インデックス - 1) / 2

インデックス 0 のないバージョン: 計算から 1 を引くだけで、結果は次のようになります:

• leftChild = インデックス * 2
• rightChild = インデックス * 2 1
• 親 = インデックス / 2

ヒープ - 最大ヒープ

最高値はルートにあるため、親ノードの値は子ノードと同じかそれより大きくなります

子と親の計算式:

• 左: leftChild = インデックス * 2 1
• 右: rightChild = インデックス * 2 2
• 親: 親 = (インデックス - 1) / 2

入れる

要素を最後に追加してバブルアップします。これにより、要素とその親が比較され、必要に応じて位置が変更されます。 O(log n).

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

取り除く

heapMax[0] 要素 (別名ルート) を削除し、最後の要素を取得してルートに移動し、sinkdown を呼び出して、正しい位置が見つかるまで新しい要素をルートから下にプッシュします。

sinkDown は、親ノードの値が子ノードの値以上であることを確認する必要があります。したがって、ノードをシンクするときは、最大の子と比較されます。

最小ヒープでは、sinkDown は親ノードの値が子の値以下であることを確認する必要があります。この場合、比較は一番小さい子と行われます。

parent = (indexDoFilho -1)/2

currentIndex = size-1

違い

• 最大ヒープでは、sinkDown は親ノードの値が子ノードの値以上であることを確認する必要があります。したがって、ノードをシンクするときは、最大の子と比較されます。
• 最大ヒープでは、親ノードがその子の最大値よりも小さい場合、最大値ができるだけ大きくなるように、最大​​の子ノードとスワップする必要があります。
• 最小ヒープでは、sinkDown は親ノードの値が子の値以下であることを確認する必要があります。この場合、比較は一番小さい子と行われます。
• 最小ヒープでは、親ノードが子ノードの最小値よりも大きい場合に切り替えが発生し、最小値が先頭に維持されます

以上がヒープ - Min e Maxの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。