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

Question

I'm using a priority queue as a scheduler with one extra requirement. I need to be able to cancel scheduled items. This equates to removing an item from the middle of the priority queue.

I can't use std::priority_queue as access to any element other than top is protected.

I'm trying to use the algorithm's heap functions. But I'm still missing the piece I need. When I remove an element I from the middle of the heap I want it to rebuild itself efficiently. C++ provides these heap functions:

• std::make_heap O(3n)
• std::push_heap O(lg(n))
• std::pop_heap O(2 lg(n))

I want a new function like std::repair_heap with a big-O < 3n. I'd provide it with location of the hole where the canceled item used to reside and it would properly adjust the heap.

It seems to be a huge oversight to not to provide a std::repair_heap function. Am I missing something obvious?

Is there library that provides an stl-compliant std::repair_heap?

Is there a better data structure for modeling a scheduler?

NOTE:
I'm not using an std::map for a few reasons.

• A heap has constant memory overhead.
• A heap has awesome cache locality.

Answer 1

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.

Answer 2

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.