在C++中只重新綁定一個元素

Question

我有一個堆棧，它建立在vector和make_heap之上。如果我改變一個（現有）元素的值，是否有O（log n）重新堆積的方法，或者我必須再次調用make_heap？

Answer 1

給你知道載體已經是一個堆，如果你決定改變埋堆內的插槽單個項目的步驟，以最小重新填充堆到有效的堆狀態包括以下內容：

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