3

我有一个建立在vectorwith上的堆make_heap。如果我只更改一个（现有）元素的值，是否有一种 O(log n) 的重新堆积方式，或者我必须make_heap再次调用整个元素？

4

1 回答 1

3

给定一个您知道的向量已经是一个堆，如果您决定更改埋在堆内的插槽中的单个项目，则将堆最小化重新填充到有效堆状态的步骤涉及以下内容：

  1. 将修改后的元素与堆中的最后一个元素交换。
  2. 从最后换入的元素执行“下推”。这涉及反复交换元素与其两个子元素中最大的元素，重复直到没有子元素或没有交换发生。注意：不要包含序列中的最后一个元素，它仍然是 #1 中的修改元素。
  3. 进行决赛push_heap(vec.begin(), vec.end())。这会将修改后的元素堆积到正确的位置。

一开始可能看起来很复杂，但除了 #2 中的步骤之外，这里并没有什么特别之处。其余的只是您可能熟悉的常规堆操作。我希望这是有道理的。

示例代码

这是一种可能的实现方式。显然，您的需求可能会有所不同。我只是把它放在一起，所以我希望它至少有点指导意义：

#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
于 2013-03-23T23:46:34.340 回答