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!

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