• Advertisement
Sign in to follow this  

std::heap

This topic is 4459 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
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.

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
Sign in to follow this  

  • Advertisement