- Home /

# 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;
openList.Add(node);
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!

**Answer** by GutoThomas
·
May 18, 2012 at 03:57 PM

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

### Your answer

### Welcome to Unity Answers

The best place to ask and answer questions about development with Unity.

To help users navigate the site we have posted a site navigation guide.

If you are a new user to Unity Answers, check out our FAQ for more information.

Make sure to check out our Knowledge Base for commonly asked Unity questions.

If you are a moderator, see our Moderator Guidelines page.

We are making improvements to UA, see the list of changes.

### Follow this Question

### Related Questions

Where are binary heaps used? 0 Answers

Change location of binary file created when saving 1 Answer

Binary Heap Minimum value 1 Answer

AI Programing Resources 9 Answers

AI Avoidance Problem 1 Answer