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

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

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×

## Important Information

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!