Tag: binary heap

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;
            }
        }
    }
}