c++ - C++で1つの要素のみを再ヒープします

Question

vectorで構築されたヒープがありますmake_heap。1つの（既存の）要素の値を変更した場合に再ヒープするO（log n）の方法はありますか、それともmake_heap全体をもう一度呼び出す必要がありますか？

Answer 1

すでにヒープであることがわかっているベクトルが与えられた場合、ヒープ内に埋め込まれたスロット内の1つのアイテムを変更する場合、ヒープを有効なヒープ状態に最小限に再設定する手順は次のとおりです。

1. 変更された要素をヒープ内の最後の要素と交換します。
2. スワップインされた要素を最後から「プッシュダウン」します。これには、要素を2つの子のうち最大のものと繰り返し交換し、子がなくなるか、交換が発生しなくなるまで繰り返します。注：シーケンスの最後の要素を含めないでください。これは、＃1から変更した要素のままです。
3. ファイナルを実行しpush_heap(vec.begin(), vec.end())ます。これにより、変更された要素が正しい位置にヒープアップされます。

最初は複雑に見えるかもしれませんが、ここでは＃2の手順以外に特別なことは何もありません。残りは、あなたがよく知っていると思われる通常のヒープ操作です。私はそれが理にかなっていることを願っています。

サンプルコード

これは可能な実装の1つです。明らかに、あなたのニーズは変わるかもしれません。私はこれを一緒に投げたので、少なくとも少し教育的であることを願っています：

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

int main()
{
    // intialize random generator
    srand((unsigned)time(0));

    // will hold our heap
    vector<int> vec;
    for (int i=0;i<20;vec.push_back(++i));
    random_shuffle(vec.begin(), vec.end());
    cout << "Rand: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // make a maxheap
    less<int> cmp;
    make_heap(vec.begin(), vec.end(), cmp);

    // dump content to stdout
    cout << "Heap: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // pick an item in the heap to modify, for our purposes, vec[1]
    vector<int>::iterator it = vec.begin()+1;
    *it *=2;

    // swap with the last element, then push-down the swapped-in element
    //  until we find its rightful home.
    iter_swap(it, vec.end()-1);
    while (distance(it, vec.end()) > 1)
    {
        // leave if no more children
        size_t i = distance(vec.begin(), it);
        if (2*i+1 >= vec.size()-1)
            break;

        // have one child. might have two
        vector<int>::iterator itChild = vec.begin() + 2*i+1;
        if (itChild+1 < vec.end()-1)
        {
            if (cmp(*itChild, *(itChild+1)))
                itChild = itChild+1;
        }

        // no need to swap; we're done.
        if (!cmp(*it, *itChild))
            break;

        // dump "before" picture
        cout << " beg: ";
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        // swap values and move to swapped child.
        iter_swap(it, itChild);
        it = itChild;

        // dump "after" picture
        cout << " end: ";
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
        cout << endl;
    }

    // now push_heap our new value, which is still hanging out
    //  at the end where we left it.
    push_heap(vec.begin(), vec.end(), cmp);

    // final dump        
    cout << "Last: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // verify make_heap likes what we made (should be the same).
    make_heap(vec.begin(), vec.end(), cmp);
    cout << "Heap: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;    

    return EXIT_SUCCESS;
}

出力

Rand: 15 14 8 5 1 17 10 13 3 20 11 19 6 4 9 2 18 7 12 16 
Heap: 20 18 19 17 16 15 10 13 12 14 11 8 6 4 9 2 5 3 7 1 
 beg: 20 1 19 17 16 15 10 13 12 14 11 8 6 4 9 2 5 3 7 36 
 end: 20 17 19 1 16 15 10 13 12 14 11 8 6 4 9 2 5 3 7 36 
 beg: 20 17 19 1 16 15 10 13 12 14 11 8 6 4 9 2 5 3 7 36 
 end: 20 17 19 13 16 15 10 1 12 14 11 8 6 4 9 2 5 3 7 36 
 beg: 20 17 19 13 16 15 10 1 12 14 11 8 6 4 9 2 5 3 7 36 
 end: 20 17 19 13 16 15 10 5 12 14 11 8 6 4 9 2 1 3 7 36 
Last: 36 20 19 13 17 15 10 5 12 16 11 8 6 4 9 2 1 3 7 14 
Heap: 36 20 19 13 17 15 10 5 12 16 11 8 6 4 9 2 1 3 7 14