namespace BinaryHeap
{
using System;
using System.Collections.Generic;
public class BinaryHeap<T> where T : IComparable<T>
{
private IList<T> heap;
public BinaryHeap(T[] elements = null)
{
if (elements != null)
{
this.heap = new List<T>(elements);
for (int i = elements.Length / 2; i >= 0; i--)
{
this.HeapifyDown(i);
}
}
else
{
this.heap = new List<T>();
}
}
public int Count
{
get
{
return this.heap.Count;
}
}
public T ExtractMax()
{
var max = this.heap[0];
this.heap[0] = this.heap[this.Count - 1];
this.heap.RemoveAt(this.Count - 1);
if (this.Count > 0)
{
this.HeapifyDown(0);
}
return max;
}
public T PeekMax()
{
var max = this.heap[0];
return max;
}
public void Insert(T node)
{
this.heap.Add(node);
this.HeapifyUp(this.Count - 1);
}
private void HeapifyDown(int i)
{
var leftChild = (i * 2) + 1;
var rightChild = (i * 2) + 2;
var biggest = i;
if (leftChild < this.Count && this.heap[leftChild].CompareTo(this.heap[biggest]) > 0)
{
biggest = leftChild;
}
if (rightChild < this.Count && this.heap[rightChild].CompareTo(this.heap[biggest]) > 0)
{
biggest = rightChild;
}
if (biggest != i)
{
T old = this.heap[i];
this.heap[i] = this.heap[biggest];
this.heap[biggest] = old;
this.HeapifyDown(biggest);
}
}
private void HeapifyUp(int i)
{
var parent = (i - 1) / 2;
while (i > 0 && this.heap[i].CompareTo(this.heap[parent]) > 0)
{
var temp = this.heap[parent];
this.heap[parent] = this.heap[i];
this.heap[i] = temp;
i = parent;
parent = (i - 1) / 2;
}
}
}
}