Heap.cs

using System;
using System.Collections;
using System.Collections.Generic;

namespace Heap
{
    public class Heap<T> : IReadOnlyCollection<T>
    {
        const int defaultCapacity = 6;

        T[] _heap;
        bool _isHeap;
        readonly IComparer<T> _comparer;

        public Heap() : this(defaultCapacity, Comparer<T>.Default) { }

        public Heap(int capacity) : this(capacity, Comparer<T>.Default) { }

        public Heap(IComparer<T> comparer) : this(defaultCapacity, comparer) { }

        public Heap(int capacity, IComparer<T> comparer)
        {
            _heap = capacity > 0 ? new T[capacity] : Array.Empty<T>();
            _comparer = comparer;
        }

        public int Count { get; private set; }

        public T Top
        {
            get
            {
                if (!_isHeap)
                    Heapify();
                return _heap[0];
            }
        }

        public void Push(T value)
        {
            if (Count == _heap.Length)
                Array.Resize(ref _heap, Count * 2);

            if (_isHeap)
                ShiftUp(Count, ref value, 0);
            else
                _heap[Count] = value;

            Count++;
        }

        public T Pop()
        {
            if (!_isHeap)
                Heapify();

            if (Count <= 0)
                return default!;

            Count--;

            T top = _heap[0];

            T x = _heap[Count];
            int index = ShiftDown(0);
            ShiftUp(index, ref x, 0);
            _heap[Count] = default!;

            return top;
        }

        void Heapify()
        {
            for (int i = Count / 2 - 1; i >= 0; i--)
            {
                T x = _heap[i];
                int index = ShiftDown(i);
                ShiftUp(index, ref x, i);
            }

            _isHeap = true;
        }

        void ShiftUp(int index, ref T x, int boundary)
        {
            while (index > boundary)
            {
                int parent = HeapParent(index);

                if (_comparer.Compare(_heap[parent], x) <= 0)
                    break;

                _heap[index] = _heap[parent];
                index = parent;
            }

            _heap[index] = x;
        }

        int ShiftDown(int index)
        {
            int parent = index;
            int leftChild = HeapLeftChild(parent);

            while (leftChild < Count)
            {
                int rightChild = HeapRightFromLeft(leftChild);
                int bestChild = rightChild < Count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0
                    ? rightChild
                    : leftChild;

                _heap[parent] = _heap[bestChild];

                parent = bestChild;
                leftChild = HeapLeftChild(parent);
            }

            return parent;
        }

        static int HeapParent(int i) => (i - 1) / 2;
        static int HeapLeftChild(int i) => i * 2 + 1;
        static int HeapRightFromLeft(int i) => i + 1;

        #region ICollection

        IEnumerator IEnumerable.GetEnumerator() => _heap.GetEnumerator();

        public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_heap).GetEnumerator();

        #endregion
    }
}