Remove an element from the middle of an std::heap

I guess you know which element in the heap container (index n) you want to delete.

1. Set the value v[n] = BIG; the value BIG is really bigger than any other values in the heap.
2. Call std::push_heap( v.begin(), v.begin()+n+1 );
3. Call std::pop_heap( v.begin(), v.end() );
4. Call v.pop_back();
5. Done

Operation is O(ln(n))

RE: request for proof

First, a qualifier: This method assumes something about the algorithm used by std push_heap.
Specifically, it assumes that std push_heap( v.begin(), v.begin()+n+1 ) will only alter the range [0, n]
for those elements which are ascendants of n, i.e., indices in the following set:

A(n)={n,(n-1)/2,((n-1)/2-1)/2....0}.  

Here is a typical spec for std push_heap:

http://www.cplusplus.com/reference/algorithm/push_heap/ "Given a heap range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location in it."

Does it guarantee to use the "normal heap algorithm" that you read about in textbooks? You tell me.

Anyway, here is the code which you can run and see, empirically, that it works. I am using VC 2005.

#include <algorithm>
#include <vector>
#include <iostream>

bool is_heap_valid(const std::vector<int> &vin)
{
    std::vector<int> v = vin;
    std::make_heap(v.begin(), v.end());
    return std::equal(vin.begin(), vin.end(), v.begin());
}


int _tmain(int argc, _TCHAR* argv[])
{
    srand(0);
    std::vector<int> v;
    for (int i=0; i<100; i++)
    {
        v.push_back( rand() % 0x7fff );
    }
    std::make_heap(v.begin(), v.end());

    bool bfail = false;
    while( v.size() >= 2)
    {
        int n = v.size()/2;
        v[n] = 0x7fffffff;
        std::push_heap(v.begin(), v.begin()+n+1);
        std::pop_heap(v.begin(), v.end());
        v.resize(v.size()-1);
        if (!is_heap_valid(v))
        {
            std::cout << "heap is not valid" << std::endl;
            bfail = true;
            break;
        }
    }
    if (!bfail)
        std::cout << "success" << std::endl;

    return 0;

}

But I have another problem, which is how to know the index "n" which needs to be deleted. I cannot see how to keep track of that (know the place in the heap) while using std push_heap and std pop_heap. I think you need to write your own heap code and write the index in the heap to an object every time the object is moved in the heap. Sigh.

Unfortunately, the standard is missing this (fairly important) function. With g++, you can use the non-standard function std::__adjust_heap to do this, but there's no easy portable way of doing it -- and __adjust_heap is slightly different in different versions of g++, so you can't even do it portably over g++ versions.

How does your repair_heap() work? Here's my guess:

If your heap is defined by some iterator range, say (heapBegin, heapEnd). The element you want to remove is the root of some subtree of the heap, which is defined by some subrange (subHeapBegin, subHeapEnd). Use std::pop_heap(subHeapBegin, subHeapEnd), then if subHeapEnd != heapEnd, swap the values at *(subHeapEnd-1) and *(heapEnd-1), which should put your deleted item at the end of the heap container. Now you have to percolate the element at *(subHeapEnd-1) up in your subheap. If I haven't missed something, which is possible, then all that remains is to chop the end element off of the heap container.

Before going to the trouble of trying to code that correctly (I've skipped some details like calculating subHeapBegin and subHeapEnd), I'd run some tests to determine if make_heap() really slows you down. Big-O is useful, but it's not the same thing as actual execution time.