# Resorting binary heaps

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

## 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 on other sites
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 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 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 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 14
• 30
• 9
• 16
• 22