using System.Collections.Generic;
using System;

public sealed class BinaryHeap<T>
{
	private readonly List<T> _elements;

	private readonly Comparison<T> _compare;

	/// <summary>
	/// The amount of elements in the heap
	/// </summary>
	public int Count => _elements.Count;

	/// <summary>
	/// A read only list of elements
	/// </summary>
	public List<T> Elements => new List<T>(_elements);

	/// <summary>
	/// Returns the method that dictates how elements are compared
	/// </summary>
	public Comparison<T> Compare => _compare;

	/// <summary>
	/// Clears the heap of all elements
	/// </summary>
	public void Clear() { _elements.Clear(); }

	/// <summary>
	/// Initialises a new BinaryHeap with the specified compare function.
	/// </summary>
	/// <param name="compare">A method used to compare elements</param>
	public BinaryHeap(Comparison<T> compare)
	{
		_compare = compare;
		_elements = new List<T>();
	}

	/// <summary>
	/// Initialises a new BinaryHeap as a copy of the passed in heap
	/// </summary>
	/// <param name="heap">The heap to copy</param>
	public BinaryHeap(BinaryHeap<T> heap)
	{
		_elements = new List<T>(heap.Elements);
		_compare = heap.Compare;
	}

	/// <summary>
	/// Extracts the root
	/// </summary>
	/// <returns>The topmost object of the heap</returns>
	public T Extract()
	{
		if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
		T node = _elements[0];

		if (_elements.Count <= 2)
			_elements.RemoveAt(0);
		else
		{
			_elements[0] = _elements[_elements.Count - 1];
			_elements.RemoveAt(_elements.Count - 1);
			BubbleDown(_elements[0]);
		}

		return node;
	}
	/// <summary>
	/// Inserts an element onto the heap
	/// </summary>
	/// <param name="entry">The object to add</param>
	public void Insert(T entry)
	{
		_elements.Add(entry);
		if ((_elements.Count - 1) == 0)
			return;

		BubbleUp(entry);

	}
	/// <summary>
	/// Peeks at the topmost object of the heap
	/// </summary>
	/// <returns>The top most object of the heap</returns>
	public T Peek()
	{
		//If a heap doesn't have any elements throw an exception
		if (_elements.Count == 0)
			throw new InvalidOperationException("The heap contains no elements");
		return _elements[0];
	}

	/// <summary>
	/// Should Element1 be swapped with Element2 based on our Compare Delegate
	/// </summary>
	/// <returns>true if it should, false if it should not</returns>
	private bool ShouldSwap(T element1, T element2)
	{
		var comparision = Compare(element1, element2);
		return comparision <= 0;
	}

	/// <summary>
	/// Swaps Element1 with Element2
	/// </summary>
	private void Swap(T element1, T element2)
	{
		//Swap the first element with the second
		int indexOfSecond = _elements.IndexOf(element2);
		_elements[_elements.IndexOf(element1)] = element2;
		_elements[indexOfSecond] = element1;


	}

	/// <summary>
	/// Bubbles the specified element down the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The Element to bubble down</param>
	private void BubbleDown(T element)
	{
		int elementIndex = _elements.IndexOf(element), minElementIndex = 0;

		while (true)
		{
			int childLeftIndex = 2 * elementIndex + 1;

			//If the Child index exists outside the amount of elements in the heap then
			//the element is already at the bottom of the heap so we should break.
			if (childLeftIndex >= _elements.Count)
				break;

			element = _elements[elementIndex];
			var childElement = _elements[childLeftIndex];

			if (ShouldSwap(childElement, element))
				minElementIndex = childLeftIndex;

			int childRightIndex = childLeftIndex + 1;

			//If the right child exists it must be checked as well
			if (childRightIndex < _elements.Count)
			{

				element = _elements[minElementIndex];
				childElement = _elements[childRightIndex];

				if (ShouldSwap(childElement, element))
					minElementIndex = childRightIndex;
			}


			//If the minimum Element is still the original element of the loop
			//then the heap properties has been restored and we should break
			if (elementIndex == minElementIndex)
				break;

			//Since our element is out of order and violating the heaps properties it should be swapped
			Swap(_elements[elementIndex], _elements[minElementIndex]);


			elementIndex = minElementIndex;
		}

	}
	/// <summary>
	/// Bubbles an Element up the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The element to bubble up</param>
	private void BubbleUp(T element)
	{
		int elementIndex = _elements.IndexOf(element);

		while (elementIndex > 0)
		{
			int parentIndex = (elementIndex - 1) / 2;

			T elementParent = _elements[parentIndex];
			if (ShouldSwap(element, elementParent))
			{
				Swap(element, elementParent);
				elementIndex = parentIndex;
			}
			else break;
		}

		_elements[elementIndex] = element;
	}
}