Reheaping only one element in c++

Question

I have a heap which was built on a vector with make_heap. Is there an O(log n) way of reheaping if I change the value of just one (existing) element, or must I call make_heap on the whole thing again?

Answer 1

Given a vector you know is already a heap, if you decide to change a single item in a slot buried within the heap the steps to minimally repopulate the heap into valid-heap-state involve the following:

1. Swap the modified element with the last element in the heap.
2. Perform a "push-down" with the swapped-in element from the end. This involves repeatedly swapping the element with the largest of its two children, repeating until there are no children left OR no swap happens. Note: Do NOT include the very last element in the sequence, which remains your modified element from #1.
3. Perform a final push_heap(vec.begin(), vec.end()). This will heap-up the modified element into its right position.

It may seem complicated at first, but there is nothing special here except the steps in #2. The rest is just regular heap operations you are likely familiar with. I hope it makes sense.

Sample Code

This is one possible implementation. Obviously your needs may vary. I just threw this together so I hope it is at least a little instructional:

#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;
}

Output

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