# Hep with binary heap poll

Hey everyone. Actually, after putting my A* to work with some Array.Sort to get the Node list adapted by F score, I’m trying to reach some better performance and finded out that the way to do this would be implementing Binary Heap into my pathfinding.

When I add an element to the list everything goes fine. It’s added in his proper position. The problem is when I want to remove an item, sometimes it seems to work, but sometimes not, and the lower F cost node still in some other position in the array which is not actually 0.

This is the code I did to do the poll from the binary heap:

``````void binaryHeapPoll(int Index) {

if(openList.Count == 0) { return; }

openList[Index] = openList[openList.Count - 1];

openList.RemoveAt(openList.Count - 1);

int current = Index;

while(current < openList.Count) {

int leftChild = leftChildOf(current);
int rightChild = rightChildOf(current);

if(rightChild < openList.Count) {

if((openList[leftChild].F < openList[current].F) && (openList[leftChild].F < openList[rightChild].F)) {

current = binaryHeapSwap(current, leftChild, false); // this just swap the two items and return me the highest index between current and leftChild

} else if ((openList[rightChild].F < openList[current].F) && (openList[rightChild].F < openList[leftChild].F)) {

current = binaryHeapSwap(current, rightChild, false);

} else { return; }

} else if (leftChild < openList.Count) {

if(openList[leftChild].F < openList[current].F) {

current = binaryHeapSwap(current, leftChild, false);
return;

} else { return; }

} else { return; }

}

}
``````

The Add method and some other methods I’m using in the binary heap you can see below:

``````int binaryHeapSwap(int indexOne, int indexTwo, bool returnMinimumIndex) {

int iOne = indexOne;
int iTwo = indexTwo;
int iMinimum = Mathf.Min(indexOne, indexTwo);
int iMaximum = Mathf.Max(indexOne, indexTwo);

Node indexOneNode = openList[iOne];
openList[iOne] = openList[iTwo];
openList[iTwo] = indexOneNode;

if(returnMinimumIndex)  {return iMinimum;}

else 					{return iMaximum;}

}

void binaryHeapOffer(Node nodeToInsert) {

Node node = nodeToInsert;

int currentIndex = openList.Count - 1;

while(currentIndex > 0) {

int parentIndex = parentOf(currentIndex);

if(openList[currentIndex].F < openList[parentIndex].F) {

currentIndex = binaryHeapSwap(currentIndex, parentIndex, true);

} else { break; }

}

}

int leftChildOf(int index) {

return ((index << 1) + 1);

}

int rightChildOf(int index) {

return ((index << 1) + 2);

}

int parentOf(int index) {

return((index - 1) >> 1);

}
``````

Really hope someone can help me with this. I spent like 3 hours last night and didn’t get any different result, but just with the poll.

Any help would be appreciated, from code to just logic tips. =)

Thanks from now!

Cheers!

The following code solve the problems!

``````void binaryHeapPoll(int Index) {

if(openList.Count == 0) { return; }

openList[Index] = openList[openList.Count - 1];

openList.RemoveAt(openList.Count - 1);

int current = Index;

while(current < openList.Count) {

int leftChild = leftChildOf(current);
int rightChild = rightChildOf(current);

if(rightChild < openList.Count) {

if((openList[leftChild].F < openList[rightChild].F)) {

if(openList[leftChild].F < openList[current].F) {

current = binaryHeapSwap(leftChild, current, false);

} else { return; }

} else {

if(openList[rightChild].F < openList[current].F) {

current = binaryHeapSwap(rightChild, current, false);

} else { return; }

}

} else if (leftChild < openList.Count) {

if(openList[leftChild].F < openList[current].F) {

current = binaryHeapSwap(current, leftChild, false);
return;

} else { return; }

} else { return; }

}

}
``````