21 private T[] _array =
new T[4];
22 private int _count = 0;
31 Array.Clear(_array, 0, _count);
37 validateHeapInternal(
"Insert");
41 if (_array.Length == _count) {
42 T[] newArray =
new T[_array.Length * 2];
43 Array.Copy(_array, newArray, _array.Length);
47 element.heapIndex = _count;
54 removeAt(element.heapIndex);
59 throw new Exception(
"Cannot peek when there are zero elements!");
67 throw new Exception(
"Cannot Remove Min when there are zero elements!");
73 private T removeAt(
int index) {
75 validateHeapInternal(
"Remove At");
78 T ret = _array[index];
85 var bottom = _array[_count];
86 bottom.heapIndex = index;
88 int parentIndex = getParentIndex(index);
89 if (isValidIndex(parentIndex) && _array[parentIndex].CompareTo(bottom) > 0) {
98 private void bubbleUp(T element) {
100 if (element.heapIndex == 0) {
104 int parentIndex = getParentIndex(element.heapIndex);
105 var parent = _array[parentIndex];
107 if (parent.CompareTo(element) <= 0) {
111 parent.heapIndex = element.heapIndex;
112 _array[element.heapIndex] = parent;
114 element.heapIndex = parentIndex;
117 _array[element.heapIndex] = element;
120 validateHeapInternal(
"Bubble Up");
125 return validateHeapInternal(
"Validation ");
128 private void bubbleDown(T element) {
129 int elementIndex = element.heapIndex;
132 int leftIndex = getChildLeftIndex(elementIndex);
133 int rightIndex = getChildRightIndex(elementIndex);
135 T smallest = element;
136 int smallestIndex = elementIndex;
138 if (isValidIndex(leftIndex)) {
139 var leftChild = _array[leftIndex];
140 if (leftChild.CompareTo(smallest) < 0) {
141 smallest = leftChild;
142 smallestIndex = leftIndex;
148 if (isValidIndex(rightIndex)) {
149 var rightChild = _array[rightIndex];
150 if (rightChild.CompareTo(smallest) < 0) {
151 smallest = rightChild;
152 smallestIndex = rightIndex;
156 if (smallestIndex == elementIndex) {
160 smallest.heapIndex = elementIndex;
161 _array[elementIndex] = smallest;
163 elementIndex = smallestIndex;
166 element.heapIndex = elementIndex;
167 _array[elementIndex] = element;
170 validateHeapInternal(
"Bubble Down");
174 private bool validateHeapInternal(
string operation) {
175 for (
int i = 0; i < _count; i++) {
176 if (_array[i].heapIndex != i) {
177 Debug.LogError(
"Element " + i +
" had an index of " + _array[i].heapIndex +
" instead, after " + operation);
182 var parent = _array[getParentIndex(i)];
183 if (parent.CompareTo(_array[i]) > 0) {
184 Debug.LogError(
"Element " + i +
" had an incorrect order after " + operation);
192 private static int getChildLeftIndex(
int index) {
193 return index * 2 + 1;
196 private static int getChildRightIndex(
int index) {
197 return index * 2 + 2;
200 private static int getParentIndex(
int index) {
201 return (index - 1) / 2;
204 private bool isValidIndex(
int index) {
205 return index < _count && index >= 0;