Sign in to follow this  
DrEvil

std::heap

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
With A*, don't you want to remove the smallest/largest element from the open list anyway? I had thought that was the point of using a heap in the first place, to reduce one part of the complexity from linear to logarithmic.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this