最大ヒープ内の最小の整数を削除する関数 HEAP-DELETE-MIN(Array) を実装する必要があります。私は関数自体を求めているわけではありませんが、誰かが 私が始めるのを助けるためにいくつかの疑似コードを提供してくれませんか? それは大きな助けになるでしょう。配列は、関数の最後に最大ヒープのままにする必要があります。
質問する
4927 次
1 に答える
6
基本的に、配列に格納されている暗黙のヒープのすべてのリーフ ノードを検索する必要があります。親はそれよりも大きくなければならず (最大ヒープ プロパティ)、リーフがインデックス n/2 以降から格納されていることがわかっているため、これはヒープのリーフ ノードになります (ただし、これはアルゴリズムの複雑さを損なうことはありません)。したがって、基本的にあなたがすべきことは次のとおりです。
1) Search the array for the minimum element
2) Place the last-inserted heap element in the position of the minimum element (essentially this is the delete)
3) Upheap the replaced node to restore maximum heap property and correct storage of the heap in the array
これは、最小要素の検索に O(n)、次にスイッチに O(1)、最後にアップヒープに O(log n) を要します。全体として、これは線形時間であり、本質的にあなたができる最善のことです。
インデックス操作には注意してください。2*i はノード i の左側の子であり、2*i+1 は配列ベースのヒープ内のノード i の右側の子です (配列の 0 番目の要素が常に空であり、ヒープのルートはインデックス 1 にあります)
于 2013-02-19T05:30:35.380 に答える