1

find-min最小-最大ヒープは、時間とfind-max操作が一定であるため、両端優先キューを実装するのに役立ちます。O(log 2 n)時間で min-max ヒープの最小要素と最大要素を取得することもできます。ただし、場合によっては、min-max ヒープ内の任意のノードを削除することもできます。これは、min-max heaps を紹介した論文によると、O(log 2 n)で実行できます。

...

構造体は、任意の固定値 (または値のセット) に対して、定数時間での操作 (構造体でk 番目Find(k)に小さい値を決定する) と対数時間での操作 (構造体で k 番目に小さい値を削除する)をサポートするように一般化することもできます。の。Delete(k)k

...

min-max ヒープで k 番目の要素を削除するにはどうすればよいですか?

4

2 に答える 2

-1

私がこのソリューションを開発することになったのは (100% 正しいとは言えません)、実際に min-max ヒープ内の任意のノードを削除するソリューションを見つけたという事実ですが、それは間違っています。

間違った解決策は、こちら( C++ で実装) とこちら(Python で実装) にあります。私は、今述べた間違った Python の解決策を紹介します。

解決策は次のとおりです。

def DeleteAt(self, position):
    """delete given position"""
    self.heap[position] = self.heap[-1]
    del(self.heap[-1])
    self.TrickleDown(position)

ここで、次の最小最大ヒープがあるとします。

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    55    65    37    31

私が確認した限り、これは有効な最小最大ヒープです。ここで、エレメント 55 を削除したいとします。このエレメントは、0 ベースの配列ではインデックス 9 にあります (カウントが正しければ)。

上記の解決策は、単純に配列の最後の要素 (この場合は 31) を配置し、それを位置 9 に配置することです。

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37    55

配列の最後の要素 (現在は 55) を削除すると、結果の最小最大ヒープは次のようになります。

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37

そして最後に、から「トリクルダウン」しますposition（つまり、現在31という数字がある場所）。

「トリクルダウン」は、偶数(または最小) または奇数(または最大) レベルにあるかどうかをチェックします。奇数レベル (3) にあるため、「トリクルダウン」は「トリクルダウン-」を呼び出します。 max" を 31 から開始しますが、31 には子がないため停止します (私が何を話しているのかわからない場合は、上記の元の論文を確認してください)。

しかし、最小-最大ヒープではない状態でデータ構造を残していることが観察された場合、偶数レベルであり、したがってその子孫よりも小さいはずの 54 が、その子孫の 1 つである 31 よりも大きいためです。

これにより、 のノードの子だけを調べるだけではなくposition、その上からも確認する必要があるのではないかと考えpositionました。「トリクルアップ」も使用する必要があるのではないでしょうか。

次の推論では、削除したい要素を削除した後、修正操作が実行される前の要素としますx。positionその親にしましょうp(存在する場合)。

私のアルゴリズムのアイデアはまさにそれであり、より具体的には次の事実に基づいています。

  1. ifxが奇数レベル (上記の例のように) にあり、それを偶数レベルにあるその parent と交換します。これは、 newの位置pから下の最小最大ヒープのルール/不変条件を破ることはありません。x.

    • 状況が逆の場合、つまり、x元々は偶数の位置にあり、親よりも大きい場合、同じ推論 (私が思うに) を行うことができます。

    • さて、気がついたなら、修正が必要な唯一のことは、 がxその親と交換され、それが現在偶数 (およびそれぞれ奇数) の位置にある場合、前の偶数 (およびそれぞれ奇数) レベルのノード。

xもちろん、これは私にとって完全な解決策ではないように思われました。もちろん、 の前の親、つまりpが正しい位置にあるかどうかも確認したかったのです。

  • pとの交換後、が奇数 (およびそれぞれ偶数) レベルにある場合x、以前は偶数 (およびそれぞれ奇数) レベルにあったため、その子孫のいずれよりも小さい (およびそれぞれ大きい) 可能性があることを意味します。だから、ここで「トリクルダウン」が必要だと思いました。

  • がその祖先に関して正しい位置にあるという事実に関してはp、推論は上記のものと似ていると思います（ただし、100％確実ではありません）。

これをまとめると、私は解決策を思いつきました：

function DELETE(H, i):

    // H is the min-max heap array
    // i is the index of the node we want to delete
    // I assume, for simplicity, 
    // it's not out of the bounds of the array

    if i is the last index of H:
        remove and return H[i]
    else:
        l = get_last_index_of(H)

        swap(H, i, l)  

        d = delete(H, l)

        // d is the element we wanted to remove initially
        // and was initially at position i
        // So, at index i we now have what was the last element of H

        push_up(H, i)

        push_down(H, i)

        return d

これは、私が作成した最小最大ヒープの実装に従って動作するようで、ここで見つけることができます。

また、ソリューションはO(log 2 n)時間で実行されることに注意してください。これは、この順序で実行される「プッシュアップ」と「プッシュダウン」を呼び出しているだけだからです。

于 2016-09-08T13:54:50.417 に答える