using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; //Generic Heap data structure class Implementation using C# //Victor Lantigua //Cuba 2019 /*heap data structure operations * extract, insert and delete * have O(log(n)) time complexity * where n is the length of the input*/ namespace Heap { public abstract class MyHeap where T: IComparable { protected int Left(int n) => 2 * n + 1; protected int Right(int n) => 2 * n + 2; protected int Father(int n) => (n - 1) / 2; protected T[] Elements; protected int size; public int Size { get { return size; } } public T First { get { if (size == 0) throw new Exception("Empity Queue"); return Elements[0]; } } public MyHeap() { Elements = new T[33]; size = 0; } protected abstract void HeapifyUp(int index); protected abstract void HeapifyDown(int index); public void Insert(T value) { if (size >= Elements.Length) Growth(); Elements[size] = value; HeapifyUp(size); size++; } protected void Growth() { T[] growup = new T[Elements.Length * 2 - 1]; this.Elements.CopyTo(growup, 0); this.Elements = growup; } public T Extract() { T value = Elements[0]; Elements[0] = Elements[size - 1]; size--; HeapifyDown(0); return value; } public void BuildHeap(T[] a) { Elements = new T[33]; size = 0; foreach (var item in a) { this.Insert(item); } } } public class MinHeap: MyHeap where T: IComparable { public MinHeap(): base() { } protected override void HeapifyUp(int index) { if (index <= 0) return; else if(Elements[Father(index)].CompareTo(Elements[index]) > 0) { T aux = Elements[Father(index)]; Elements[Father(index)] = Elements[index]; Elements[index] = aux; HeapifyUp(Father(index)); } } protected override void HeapifyDown(int index) { if (Left(index) >= size) return; if (Right(index) == size) { if(Elements[Left(index)].CompareTo(Elements[index]) < 0) { T aux = Elements[Left(index)]; Elements[Left(index)] = Elements[index]; Elements[index] = aux; } return; } int change = Elements[Right(index)].CompareTo(Elements[Left(index)]) < 0 ? Right(index): Left(index); if ((Elements[change].CompareTo(Elements[index]) < 0)) { T AUX = Elements[index]; Elements[index] = Elements[change]; Elements[change] = AUX; HeapifyDown(change); } } } public class MaxHeap : MyHeap where T : IComparable { public MaxHeap() : base() { } protected override void HeapifyUp(int index) { if (index <= 0) return; else if (Elements[Father(index)].CompareTo(Elements[index]) < 0) { T aux = Elements[Father(index)]; Elements[Father(index)] = Elements[index]; Elements[index] = aux; HeapifyUp(Father(index)); } } protected override void HeapifyDown(int index) { if (Left(index) >= size) return; if (Right(index) == size) { if (Elements[Left(index)].CompareTo(Elements[index]) > 0) { T aux = Elements[Left(index)]; Elements[Left(index)] = Elements[index]; Elements[index] = aux; } return; } int change = Elements[Right(index)].CompareTo(Elements[Left(index)]) > 0 ? Right(index) : Left(index); if ((Elements[change].CompareTo(Elements[index]) > 0)) { T AUX = Elements[index]; Elements[index] = Elements[change]; Elements[change] = AUX; HeapifyDown(change); } } } }

Heap data structure class implementation using C#