🔒 Locked

Resorting binary heaps

Started by SFCBias Dec 10, 2011 at 7:59 AM 3 replies 1.2k views

Original Post

Dec 10, 2011 at 7:59 AM

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)?

SiCrane

Dec 10, 2011 at 3:12 PM

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.

SFCBias

Dec 10, 2011 at 5:54 PM

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);
 }
 }

alvaro

Dec 10, 2011 at 6:04 PM

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

SFCBias

Dec 11, 2011 at 10:50 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.