Remove the element from the middle of std :: heap

Question

I use the priority queue as a scheduler with one additional requirement. I need to cancel the scheduled items. This is equivalent to removing an item from the middle of the priority queue.

I can not use std::priority_queue , since access to any element other than the top one is protected.

I am trying to use the heap functions of an algorithm . But I'm still missing the part I need. When I delete an item from the middle of the heap, I want it to be restored efficiently. C ++ provides the following heap functions:

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

I need a new function like std::repair_heap with big-O <3n. I would give him a place for the hole in which the element that was used was canceled, and it would correctly adjust the heap.

There seems to be a std::repair_heap control over not providing the std::repair_heap . Am I missing something?

Is there a library that provides stl-compatible std::repair_heap ?

Is there a better data structure for modeling the scheduler?

Note :
I do not use std::map for several reasons.

• The heap has a fixed memory overhead.
• The heap has an amazing cache locality.

Answer 1

Unfortunately, the standard lacks this (rather important) function. With g ++, you can use the non-standard function std::__adjust_heap to do this, but there is no easy portable way to do this - and __adjust_heap slightly different in different versions of g ++, so you can’t even do this portablely over g ++ versions.

Answer 2

How does your repair_heap() ? Here is my hunch:

If your heap is determined by some range of iterator, say (heapBegin, heapEnd). The item you want to delete is the root of some heap subtree, which is determined by some sub-range (subHeapBegin, subHeapEnd). Use std::pop_heap(subHeapBegin, subHeapEnd) , then if subHeapEnd != heapEnd , change the values ​​to *(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 in * (subHeapEnd-1) up in your sub-item. If I did not miss something that is possible, then all that remains is to cut the final element from the heap container.

Before trying to code it correctly (I skipped some details, such as calculating subHeapBegin and subHeapEnd), I would run some tests to determine if make_heap() really slows you down. Big-O is useful, but it's not the same as the actual runtime.

Answer 3

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

• Set the value v[n] = BIG; , the BIG value is really larger than any other values ​​on the heap.
• Call std::push_heap( v.begin(), v.begin()+n+1 );
• Call std::pop_heap( v.begin(), v.end() );
• Call v.pop_back();
• Done

Operation O (ln (n))

RE: confirmation request

First, the qualifier: This method assumes something about the algorithm used by std push_heap.
In particular, it is assumed that std push_heap (v.begin (), v.begin () + n + 1) will change the range [0, n]
for those elements that are descendants 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 specification for std push_heap:

http://www.cplusplus.com/reference/algorithm/push_heap/ "Given the heap range of [first, last-1], this function extends the range considered by the heap to [first, last] by putting the value in (last-1) to the appropriate place in it. "

Does this guarantee the use of the “regular heap algorithm” that you read about in textbooks? You tell me.

In any case, here is the code that 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 find out the index "n" that needs to be removed. I don’t see how to track this (I know the place on the heap) using std push_heap and std pop_heap. I think you need to write your own heap code and write an index on the heap for the object every time the object is moved to the heap. Sigh.

Answer 4

It seems to me that removing from the middle of the heap may mean that the whole heap needs to be rebuilt: the reason is that there is no repair, because it would have to do the same (big-o) job as make_heap .

Can you do something like put std::pair<bool, Item> on the heap and just invalidate the elements instead of deleting them? Then, when they finally get to the top, they simply ignore the subject and move around.

Answer 5

Here is some delphi code that I used to remove items from the heap. I don't know this C ++ you are talking about, and I don't have a restore function, but hey ..

pop first so you understand how it works:

 function THeap.Pop: HeapItem; begin if fNextIndex > 1 then begin Dec(fNextIndex); Result:= fBuckets[1]; //no zero element fBuckets[1] := fBuckets[fNextIndex]; fBuckets[fNextIndex] := nil; FixHeapDown; //this has a param defaulting to end else Result:= nil; end; 

now for comparison, removal:

 procedure THeap.Delete(Item: HeapItem); var i:integer; begin for i:=1 to pred(fNextIndex) do if Item=fBuckets[i] then begin dec(fNextIndex); fBuckets[i] := fBuckets[fNextIndex]; fBuckets[fNextIndex] := nil; FixHeapDown(i); break; end; end; 

he, of course, is no, no, to even think about doing what we are doing here, but hey, it costs sometimes to change, and tasks are canceled.

enjoy. I hope this helps.