Jump to content
  • Advertisement
Sign in to follow this  
SFCBias

Resorting binary heaps

This topic is 2564 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

I have a minimum ordered binary heap. (I'm using A* pathfinding) at one point or another I come to a point where I must modify a node that may or may not be the top or bottom of the tree.
How would I go about resorting the entire array (since, I don't know the exact position within the heap of the node i modified)?

Share this post


Link to post
Share on other sites
Advertisement
You might want to mention some implementation details like what language you're using, if you're using an existing heap class or heap functions, etc. Ex: if you're using C++ and the standard library heap functions you could just re-call std::make_heap on the array.

Share this post


Link to post
Share on other sites
Woops, sorry. I'm using C++ and I wrote the heap class myself. I actually came across a method of doing what i was looking for and implemented it this morning.

void heapify(int pos = 1)
{
assert(pos > 0 && pos <= mNumItems);
T _parent = mHeap[pos];

int leftPos = int(pos * 2);
int rightPos = int(pos * 2) + 1;

T _left = mHeap[leftPos];
T _right = mHeap[rightPos];

int smallestPos = pos;
T _smallest = _parent;

if (leftPos <= mNumItems && compare(_left, _parent))
{
_smallest = _left;
smallestPos = leftPos;
}

if (rightPos <= mNumItems && compare(_right, _smallest))
{
_smallest = _right;
smallestPos = rightPos;
}

if (smallestPos != pos)
{
mHeap[pos] = mHeap[smallestPos];
mHeap[smallestPos] = _parent;
heapify(smallestPos);
}
}

Share this post


Link to post
Share on other sites
I can't imagine why you wouldn't have the index available. If you can modify the element, it means you have a way of knowing where in the array the node is. Fixing the heap should only take time O(log(n)), but heapify is O(n).

Share this post


Link to post
Share on other sites
Because i'm not directly modifiying the element from the heap. After i pop the root element which is a node, i modify one of it's neighbors which i don't know the index of within the heap.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!