Wow, so apparently MS added a bunch of debug code to various stl algorithms and such with msvc 2005 which I just recently began using for my projects. The new debugging pointed out some problems in how I was using std::push_heap I'm using std::push_heap along with an std::vector for my A* open list. When I removed and re-inserted nodes on the open list, the new debug code is asserting with an "invalid heap" message. This made me realize that when I'm removing from the heap with vector.erase, I'm jacking up the heap. My question is, after I .erase, I need to do std::make_heap again to rebuild the heap correct? After doing this, things seem to work ok without any further asserts, but I'm wondering if anyone knows a more efficient method of rebuilding the heap than std::make_heap, since it doesn't seem very efficient judging by the msdn description "The complexity is linear, requiring 3 * (_Last – _First) comparisons." Anyone have any ideas? Or is make_heap my only option? Thanks.

pop_heap only "Removes the largest element from the front of a heap to the next-to-last position in the range and then forms a new heap from the remaining elements."

when removing & re-inserting into the open list in a*, it wont be the one popped.
ie. it doesnt work for popping arbitrary elements

Why do you need to remove arbitrary entries in your open list? The idea in A* is to expand the best node, which with a proper heap should always be the top.

Yes, I always pop_back when exploring the next best node, but in some variations of A*, when the path is expanding, if you reach a node that is in the open list already, and the new cost to this node is cheaper than whats in the open list, you favor this newly found path, which requires the node to be removed and re-inserted with the new cost.

Hey Jeremy, if you're using a binary heap reorganizing should only be O(lg(n)) not linear; is there an alternative to make_heap? I suspect because its a compiler implementation the internal HEAPIFY procedure to reorganize the heap will return after it recoginizes the heap property has been satisfied and if you're removing from the front of the array, that should be lg(n).

The removal and re-insertion into the open list isn't at the top of the heap, it could be anywhere.

The reason for this is explained in the 3rd paragraph under "set representation"

http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

As explain there, not every removal in A* is from the top of the heap.