7

ヒープから最大値のオブジェクトを継続的に抽出して処理するコードがあります。ただし、最大の処理中に、ヒープ内の他のオブジェクトが影響を受けるため、削除する必要がある場合があります。だいたい：

vector<HeapEntry*> myHeap = vector<HeapEntry*>();
fillHeap(myHeap, someData);
make_heap(myHeap.begin(), myHeap.end());
while (!myHeap.empty())
{
    HeapEntry* hp = myHeap.front();
    HeapEntry* neighbor = hp->getNeighbor();
    if (someCondition)
    {
        remove(myHeap, neighbor);
    }
    //more processing of hp
}

そして削除機能：

void remove(vector<HeapEntry*> myHeap, HeapEntry* toRemove)
{
    for (it = myHeap.begin(); it != myHeap.end(); it++)
    {
        if (*it == hp)
        {
            myHeap.erase(it);
            break;
        }
    }
    make_heap(myHeap.begin(), myHeap.end());
}

これが実行され、正しい出力が得られます。しかし、40kb のファイルを処理するのに 2 分かかります (ヒープのサイズはファイルのサイズに比例します)。とにかく効率化が必要です。

remove 関数は、およそ n 回呼び出されることになります。ここで、n はヒープのサイズです。したがって、その線形検索を行うと、アルゴリズム全体が O(n^2) になります。それが問題だと思います。これは O(n*log(n)) で実行できると思います。

私の目標は、削除機能を O(log(n)) 時間で実行することです。何かのようなもの：

  • 目的の要素に直行
  • 最後の要素で切り替える
  • pop_heap(myHeap.begin(), myHeap.end()); myHeap.pop_back();
  • make_heap(myHeap.begin(), myHeap.end());

これを実装する方法がよくわかりません (stl ヒープにはほとんど慣れていません)。線形検索を行わずにこれを行う方法を知っている人はいますか?

4

4 に答える 4

5

簡単な方法は、削除したいと思う要素を削除しないことです。代わりに、優先キューを維持して、次の最大要素とstd::set<HeapEntry*>削除された要素を決定します。最大要素を取得するときに、それが削除された要素のセットにあるかどうかを確認し、ヒープから削除して、次の要素を試します。削除される可能性のある要素の数によっては、要素をヒープから削除するときに、削除された要素のセットから要素を削除することもできます。

ヒープから要素を削除する代わりに、削除された要素のセットに要素を追加するだけです。このようにして、ヒープ要素は依然として対数のままであり、要素のセットに対して最大 O(n log n) の操作を行うことができます。

もう 1 つの方法は、ノードベースのプライオリティ キューを使用して、ヒープ内のノードの位置を効率的に見つけることです。たとえば、Boost は、Boost グラフ ライブラリの一部としてフィボナッチ ヒープを提供します。そこで要素の位置を追跡できます。ただし、ノードベースのヒープは、要素を再配置するときのオーバーヘッドのために、実際の問題サイズではパフォーマンスが低下する傾向があります。

于 2012-09-24T19:36:01.707 に答える
2

返信ありがとうございます。HeapEntries が無効になったときに実際に削除するアプローチを採用することにしました。実際、私は有効なフラグを HeapEntry に追加しようとしましたが、それ以降に修正した他のエラーがなければ、これはうまくいったと思います。とにかく、これが私がそれを解決した方法です。

繰り返しになりますが、要素へのポインターだけが与えられた場合に、ヒープから要素を削除する機能が必要でした。問題は、ポインターが位置について何も教えてくれなかったことです。ヒープ内の要素の。そこで、位置を保存し、要素が移動するたびに位置を更新し、位置を指定してヒープから削除する関数を作成することにしました。簡単に言えば、ヒープは配列として格納され、要素の位置によって親子関係が定義されます。要素の親は位置 floor((myPos - 1) / 2) にある必要があり、その子は位置 2*myPos+1 および 2*myPos+2 にある必要があります。remove(position) 関数を記述できることに気付きました。ヒープ プロパティを維持するために要素を交換しながら、格納されている位置も交換できることに気付きました。結果へのリンクは次のとおりです。これにより、実行が 5 倍または 10 倍高速化されました。

https://github.com/yankrasny/CC-Heap-with-random-delete

于 2012-11-04T20:42:56.330 に答える
1

stl の哲学は、最初にアルゴリズムを検討してから、データ構造を選択することです。あなたはそれを逆にやっています。

データ構造から要素を「ランダムな」順序で削除する場合は、おそらくpriority_queueリンクされlistた . (ただし注意してください: 一部の stl コンテナーから削除すると、イテレーターが無効になる場合があります)。

于 2012-09-24T18:55:42.313 に答える