ADN.DataStructures by Andrés Di Giovanni

<PackageReference Include="ADN.DataStructures" Version="1.3.0" />

 Heap<T>

public abstract class Heap<T> : IHeap<T> where T : IComparable
using System; namespace ADN.DataStructures { public abstract class Heap<T> : IHeap<T> where T : IComparable { protected T[] _heap; public int Count { get; set; } public bool IsEmpty => Count == 0; protected Heap(int minSize) { _heap = new T[(int)Math.Pow(2, Math.Ceiling(Math.Log((double)minSize, 2)))]; } public void Insert(T val) { if (Count == _heap.Length) DoubleHeap(); _heap[Count] = val; ShiftUp(Count); Count++; } public T Peek() { if (_heap.Length == 0) throw new ArgumentOutOfRangeException("No values in heap"); return _heap[0]; } public T Remove() { T result = Peek(); Count--; _heap[0] = _heap[Count]; ShiftDown(0); return result; } private void ShiftUp(int heapIndex) { if (heapIndex != 0) { int num = (heapIndex - 1) / 2; if (DoCompare(num, heapIndex) > 0) { Swap(num, heapIndex); ShiftUp(num); } } } private void ShiftDown(int heapIndex) { int num = heapIndex * 2 + 1; if (num < Count) { int num2 = num + 1; int num3 = (num2 >= Count || DoCompare(num, num2) <= 0) ? num : num2; if (DoCompare(num3, heapIndex) <= 0) { Swap(heapIndex, num3); ShiftDown(num3); } } } private void Swap(int index1, int index2) { T val = _heap[index1]; _heap[index1] = _heap[index2]; _heap[index2] = val; } protected abstract int DoCompare(int initialIndex, int contenderIndex); private void DoubleHeap() { T[] array = new T[_heap.Length * 2]; for (int i = 0; i < _heap.Length; i++) { array[i] = _heap[i]; } _heap = array; } } }