This is my attempt at implementing a Binary heap. I made an abstract base class Heap with an abstract property controlling whether it is a min-heap or a max-heap.
One thing I've been struggling with was which collections.generic interfaces to apply to the class. Enumerating the heap only makes a bit of sense. At the same time, it is a collection, but I'm not sure if all the interface methods really make sense for a Heap. So any pointers for that would be welcome.
Abstract Heap<T>
public abstract class Heap<T> : IEnumerable<T>, ICollection<T> where T : IComparable {
private T[] innerT;
private int capacity = 1;
private int numberOfLevels = 1;
public int Count { get; private set; } = 0;
public bool IsReadOnly => false;
protected abstract bool CloserToRoot(int comparison);
public Heap() {
innerT = new T[capacity];
}
public Heap(int capacity) {
innerT = new T[capacity];
this.capacity = capacity;
this.numberOfLevels = CapacityToLevels(capacity);
}
public Heap(IEnumerable<T> sequence) {
if (sequence == null) {
throw new ArgumentNullException(nameof(sequence));
}
foreach (var item in sequence) {
Add(item);
}
}
public void Add(T item) {
Count++;
if (Count == capacity) {
Resize();
}
innerT[Count - 1] = item;
UpHeap();
}
private int Find(T item) {
return FindInternal(item, 0);
}
private int FindInternal(T item, int index) {
if (index >= Count) {
return -1; // end of the heap.
}
var comp = innerT[index].CompareTo(item);
if (comp == 0) { // Found it!
return index;
} else if (CloserToRoot(comp)) { // Still possible to be lower.
var rightChild = IndexToRightChildNode(index);
var leftChild = rightChild - 1;
var rightResult = FindInternal(item, rightChild);
var leftResult = FindInternal(item, leftChild);
if (rightResult >= 0) {
return rightResult;
}
if (leftResult >= 0) {
return leftResult;
}
}
return -1; // Nope :( Either both children were -1 or this index has a value lower than item;
}
private void UpHeap() {
var currentNode = Count - 1;
var parentNode = IndexToParentNode(currentNode);
while (currentNode != 0 && CloserToRoot(innerT[currentNode].CompareTo(innerT[parentNode]))) {
Swap(currentNode, parentNode);
currentNode = parentNode;
parentNode = IndexToParentNode(currentNode);
}
}
private void DownHeap(int startingIndex) {
int currentIndex;
var largestIndex = startingIndex;
do {
currentIndex = largestIndex;
var rightChild = IndexToRightChildNode(currentIndex);
var leftChild = rightChild - 1;
if (leftChild < Count && CloserToRoot(innerT[leftChild].CompareTo(innerT[largestIndex]))) {
largestIndex = leftChild;
}
if (rightChild < Count && CloserToRoot(innerT[rightChild].CompareTo(innerT[largestIndex]))) {
largestIndex = rightChild;
}
Swap(largestIndex, currentIndex);
} while (largestIndex != currentIndex);
}
private void Swap(int a, int b) {
var placeholder = innerT[a];
innerT[a] = innerT[b];
innerT[b] = placeholder;
}
private static int CapacityToLevels(int capacity) {
var Log2 = Math.Log(2);
return (int)Math.Ceiling(Math.Log(capacity + 1) / Log2);
}
private static int IndexToRightChildNode(int index) {
return 2 * index + 2;
}
private static int IndexToParentNode(int index) {
return (index - 1) / 2;
}
private void Resize() {
capacity = capacity << 1 | 1;
numberOfLevels++;
Array.Resize(ref innerT, capacity);
}
public IEnumerator<T> GetEnumerator() {
return (IEnumerator<T>)innerT.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() {
return innerT.GetEnumerator();
}
public void Clear() {
capacity = 1;
numberOfLevels = 1;
innerT = new T[capacity];
}
public bool Contains(T item) {
return Find(item) != -1;
}
public void CopyTo(T[] array, int arrayIndex) {
if (arrayIndex < 0 || arrayIndex >= Count) {
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
}
innerT.CopyTo(array, arrayIndex);
}
public bool Remove(T item) {
var index = Find(item);
if (index == -1) {
return false;
}
innerT[index] = default(T);
Swap(index, Count - 1);
Count--;
DownHeap(index);
return true;
}
}
MaxHeap
public class MaxHeap<T> : Heap<T> where T : IComparable {
public MaxHeap() {
}
public MaxHeap(int capacity) : base(capacity) {
}
public MaxHeap(IEnumerable<T> sequence) : base(sequence) {
}
protected override bool CloserToRoot(int comparison) => comparison > 0;
}
MinHeap
public class MinHeap<T> : Heap<T> where T : IComparable {
public MinHeap() {
}
public MinHeap(int capacity) : base(capacity) {
}
public MinHeap(IEnumerable<T> sequence) : base(sequence) {
}
protected override bool CloserToRoot(int comparison) => comparison < 0;
}
CompareTois not guaranteed to return -1..+1, only the sign (or zero) is relevant. \$\endgroup\$ComparisonDirectionshould be replaced by aboolmethod. \$\endgroup\$numberOfLevelsfor? It seems to be maintained but not used \$\endgroup\$