koobas.hobune.stream
Binary Heap Minimum value
Hi, I have this script to get an object with a lowest variable value. However if I run it I get an error IndexOutOfRangeException on the first line(12) of the Add function. Any ideas?
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class BinaryHeap : MonoBehaviour
{
public GameObject[] binaryHeap;
private int numberOfItems;
public void Add(GameObject fCost)
{
this.binaryHeap[this.numberOfItems] = fCost;
int bubbleIndex = this.numberOfItems;
while (bubbleIndex != 1)
{
int parentIndex = bubbleIndex / 2;
if (this.binaryHeap[bubbleIndex].GetComponent<Node>().f_totalCost <= this.binaryHeap[parentIndex].GetComponent<Node>().f_totalCost)
{
GameObject tmpValue = this.binaryHeap[parentIndex];
this.binaryHeap[parentIndex] = this.binaryHeap[bubbleIndex];
this.binaryHeap[bubbleIndex] = tmpValue;
bubbleIndex = parentIndex;
}
else
{
break;
}
}
this.numberOfItems++;
}
public GameObject Remove()
{
this.numberOfItems--;
GameObject returnItem = this.binaryHeap[1];
this.binaryHeap[1] = this.binaryHeap[this.numberOfItems];
int swapItem = 1, parent = 1;
do {
parent = swapItem;
if ((2 * parent + 1) <= this.numberOfItems)
{
if (this.binaryHeap[parent].GetComponent<Node>().f_totalCost >= this.binaryHeap[2 * parent].GetComponent<Node>().f_totalCost)
{
swapItem = 2 * parent;
}
if (this.binaryHeap[swapItem].GetComponent<Node>().f_totalCost >= this.binaryHeap[2 * parent + 1].GetComponent<Node>().f_totalCost)
{
swapItem = 2 * parent + 1;
}
}
else if ((2 * parent) <= this.numberOfItems)
{
if (this.binaryHeap[parent].GetComponent<Node>().f_totalCost >= this.binaryHeap[2 * parent].GetComponent<Node>().f_totalCost)
{
swapItem = 2 * parent;
}
}
if (parent != swapItem)
{
GameObject tmpIndex = this.binaryHeap[parent];
this.binaryHeap[parent] = this.binaryHeap[swapItem];
this.binaryHeap[swapItem] = tmpIndex;
}
}
while (parent != swapItem);
return returnItem;
}
}
nope but I've tried setting it to 0 and 1 (it should be one) during declaration and no change. I think the problem is that the field is not declared however I can't hardcode the length since I will be adding and removing stuff. I've also tried using list array ins$$anonymous$$d of an array which should be dynamic but still the same error
Use a generic List. This is what they are designed for. Psuedo code
using system.collections.generic;
public List<GameObjec> binaryHeap = new List<GameObject>();
binaryHeap.Add(fCost);
The other option is to resize your array every time you add an element. Which is basically the same thing a list does, but will require you to write more code.
Actually rereading your question there is probably a specific collection type in system.collections.generic that will do the job for you without any extra coding. Worth checking out.
well I was trying to avoid list as there should be a drop in performance. As I understand it lists are actually looped through when you want to access a variable in contrast to arrays where you can access it directly
Resizing an array isn't cheap either.
Have you actually had performance issues using a list?
Build code that works first, optimise it later if it becomes an issue.
yes I had. its part of a pathfinding which needs to be much faster than it currently is. unfortunately c# doesn't support priority queue.
so it turns out list actually uses an array and you can access it via index so it is very efficient when used right. btw this is a very useful article about containers and their pros and cons
thanks for help :)
