BinaryHeap.cs

public class BinaryHeap<T>
{
	private readonly IComparer<T> m_comparer;
	private readonly IList<T> m_values;

	private int m_offset;

	public int Capacity => m_values.Count;
	public int Count => m_offset;

	public BinaryHeap(IList<T> values, IComparer<T> comparer) {
		m_comparer = comparer;
		m_offset = values.Count;
		m_values = values;

		Build();
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public T Peek() {
		return m_values[0];
	}
	public T Pop() {
		if (TryPop(out T value)) {
			return value;
		}
		else {
			throw new InvalidOperationException(message: "heap is empty");
		}
	}
	public int Push(T value) {
		var offset = Count;

		if (Capacity <= offset) {
			m_values.Add(default);
		}

		while (0 < offset) {
			var parent = ((offset - 1) >> 1);

			if (m_comparer.Compare(m_values[parent], value) > 0) {
				break;
			}

			m_values[offset] = m_values[parent];
			offset = parent;
		}

		m_values[offset] = value;

		return m_offset++;
	}
	public T Replace(T newValue) {
		if (TryReplace(newValue, out T oldValue)) {
			return oldValue;
		}
		else {
			throw new InvalidOperationException(message: "heap is empty");
		}
	}
	public bool TryPop(out T value) {
		if (0 < Count) {
			value = Peek();
			m_values[0] = m_values[--m_offset];
			m_values[m_offset] = default;

			Sieve();

			return true;
		}
		else {
			value = default;

			return false;
		}
	}
	public bool TryReplace(T newValue, out T oldValue) {
		if (0 < Count) {
			oldValue = Peek();
			m_values[0] = newValue;

			Sieve();

			return true;
		}
		else {
			oldValue = default;

			return false;
		}
	}

	private void Build() {
		BinaryHeap.Build(m_values, m_comparer, m_offset);
	}
	private void Sieve() {
		BinaryHeap.Sieve(m_values, m_comparer, 0, m_offset);
	}
}

public static class BinaryHeap
{
	public static void Build<T>(IList<T> values, IComparer<T> comparer, int count) {
		for (var offset = ((count - 1) >> 1); (-1 < offset); offset--) {
			Sieve(values, comparer, offset, count);
		}
	}
	public static void Sieve<T>(IList<T> values, IComparer<T> comparer, int offset, int count) {
		while (offset < count) {
			var left = ((offset << 1) + 1);
			var right = (left + 1);
			var parent = offset;

			if ((left < count) && (0 < comparer.Compare(values[left], values[parent]))) {
				parent = left;
			}

			if ((right < count) && (0 < comparer.Compare(values[right], values[parent]))) {
				parent = right;
			}

			if (offset == parent) {
				return;
			}

			var temp = values[offset];

			values[offset] = values[parent];
			values[parent] = temp;

			offset = parent;
		}
	}
	public static void Sort<T>(IList<T> values, IComparer<T> comparer) {
		var count = values.Count;

		Build(values, comparer, count);

		for (var offset = (count - 1); (0 < offset); offset--) {
			var temp = values[0];

			values[0] = values[offset];
			values[offset] = temp;

			Sieve(values, comparer, 0, offset);
		}
	}
	public static void Sort<T>(IList<T> values) {
		Sort(values, Comparer<T>.Default);
	}
}