An efficient binary heap for C#.

CoderoddeBinaryHeap.cs

namespace CR.PriorityQueues
{
    class CoderoddeBinaryHeap<TElement, TPriority> : PriorityQueue<TElement, TPriority>
        where TElement : notnull
        where TPriority : notnull
    {
        private static readonly int INITIAL_CAPACITY = 16;

        private class HeapNode<Element, Priority> where Element : notnull where Priority : notnull
        {
            public Element element;
            public Priority priority;
            public int index;

            public HeapNode(Element element, Priority priority)
            {
                this.element = element;
                this.priority = priority;
            }

            public string ToString()
            {
                return "[" + element.ToString() + " - " + priority.ToString() + ", index: " + index + "]";
            }
        }

        private int size;
        private HeapNode<TElement, TPriority>[] heapNodeArray =
            new HeapNode<TElement, TPriority>[INITIAL_CAPACITY];

        private readonly Dictionary<TElement, HeapNode<TElement, TPriority>> map = new();

        public IComparer<TPriority> Comparer { get; }

        public CoderoddeBinaryHeap()
        {
            Comparer = Comparer<TPriority>.Default;
        }

        public CoderoddeBinaryHeap(IComparer<TPriority> comparer)
        {
            Comparer = comparer;
        }

        public int Count => size;

        public void Enqueue(TElement item, TPriority priority)
        {
            if (map.TryGetValue(item, out var node))
            {
                node.priority = priority;
                SiftUp(node.index);
                SiftDown(node.index);
            }
            else
            {
                if (IsFull())
                {
                    ExtendHeapNodeArray();
                }

                HeapNode<TElement, TPriority> newNode = new HeapNode<TElement, TPriority>(item, priority);
                newNode.index = size;
                heapNodeArray[size] = newNode;
                size++;
                SiftUp(size - 1);
                map[item] = newNode;
            }
        }

        public bool Dequeue(out TElement element, out TPriority priority)
        {
            if (size == 0)
            {
                (element, priority) = (default, default);
                return false;
            }

            HeapNode<TElement, TPriority> node = heapNodeArray[0];
            size--;
            heapNodeArray[0] = heapNodeArray[size];
            node.index = 0;
            SiftDown(0);
            (element, priority) = (node.element, node.priority);
            heapNodeArray[size] = null;

            if (ShouldShrink())
            {
                ShrinkHeapNodeArray();
            }

            return true;
        }

        private void SiftUp(int index)
        {
            HeapNode<TElement, TPriority> node = heapNodeArray[index];
            TPriority priority = node.priority;

            while (index > 0)
            {
                int parentIndex = (index - 1) / 2;
                HeapNode<TElement, TPriority> parentNode = heapNodeArray[parentIndex];

                if (Comparer.Compare(priority, parentNode.priority) < 0)
                {
                    heapNodeArray[index] = parentNode;
                    parentNode.index = index;
                    index = parentIndex;
                }
                else
                {
                    break;
                }
            }

            heapNodeArray[index] = node;
            node.index = index;
        }
        private void SiftDown(int index)
        {
            HeapNode<TElement, TPriority> node = heapNodeArray[index];
            TPriority priority = node.priority;

            while (true)
            {
                int minimumChildIndex;
                int leftChildIndex = 2 * index + 1;

                if (leftChildIndex < size)
                {
                    minimumChildIndex = leftChildIndex;
                }
                else
                {
                    heapNodeArray[index] = node;
                    node.index = index;
                    return;
                }

                int rightChildIndex = leftChildIndex + 1;

                if (rightChildIndex < size && Compare(rightChildIndex, leftChildIndex))
                {
                    minimumChildIndex = rightChildIndex;
                }

                if (Comparer.Compare(priority, heapNodeArray[minimumChildIndex].priority) > 0)
                {
                    heapNodeArray[index] = heapNodeArray[minimumChildIndex];
                    heapNodeArray[index].index = index;

                    index = minimumChildIndex;
                    leftChildIndex = index * 2 + 1;
                    rightChildIndex = leftChildIndex + 1;
                }
                else
                {
                    heapNodeArray[index] = node;
                    node.index = index;
                    return;
                }
            }
        }

        private bool IsFull()
        {
            return size == heapNodeArray.Length;
        }

        private void ExtendHeapNodeArray()
        {
            HeapNode<TElement, TPriority>[] newHeapNodeArray =
            new HeapNode<TElement, TPriority>[heapNodeArray.Length * 2];
            Array.Copy(heapNodeArray, 0, newHeapNodeArray, 0, size);
            heapNodeArray = newHeapNodeArray;
        }

        private bool ShouldShrink()
        {
            return heapNodeArray.Length / 2 != INITIAL_CAPACITY &&
                4 * size <= heapNodeArray.Length;
        }

        private void ShrinkHeapNodeArray()
        {
            HeapNode<TElement, TPriority>[] newHeapNodeArray =
            new HeapNode<TElement, TPriority>[heapNodeArray.Length / 2];
            Array.Copy(heapNodeArray,
                       0,
                       newHeapNodeArray,
                       0,
                       newHeapNodeArray.Length);

            heapNodeArray = newHeapNodeArray;
        }

        private bool Compare(int leftIndex, int rightIndex) =>
            Comparer.Compare(heapNodeArray[leftIndex].priority,
                             heapNodeArray[rightIndex].priority) < 0;
    }
}

MyPriorityQueue.cs

using System.Collections.Generic;

namespace CR.PriorityQueues
{
    class MyPriorityQueue<TElement, TPriority> : PriorityQueue<TElement, TPriority>
    where TElement : notnull
    {
        private readonly List<(TElement Element, TPriority Priority)> heap = new();
        private readonly Dictionary<TElement, int> itemIndices = new();

        public MyPriorityQueue() => Comparer = Comparer<TPriority>.Default;
        public MyPriorityQueue(IComparer<TPriority> comparer) => Comparer = comparer;

        public int Count => heap.Count;
        public IComparer<TPriority> Comparer { get; }

        public void Enqueue(TElement item, TPriority priority)
        {
            if (itemIndices.TryGetValue(item, out int index))
            {
                heap[index] = (item, priority);
                BubbleUp(index);
                BubbleDown(index);
            }
            else
            {
                heap.Add((item, priority));
                itemIndices[item] = Count - 1;
                BubbleUp(Count - 1);
            }
        }

        public bool Dequeue(out TElement element, out TPriority priority)
        {
            if (Count == 0)
            {
                (element, priority) = (default, default);
                return false;
            }

            var minItem = heap[0];
            heap[0] = heap[^1];
            itemIndices[heap[0].Element] = 0;

            heap.RemoveAt(Count - 1);
            if (Count > 0)
            {
                BubbleDown(0);
            }

            (element, priority) = minItem;
            return true;
        }

        private void BubbleUp(int index)
        {
            while (index > 0)
            {
                var parentIndex = (index - 1) / 2;
                if (Compare(index, parentIndex))
                {
                    Swap(index, parentIndex);
                    index = parentIndex;
                }
                else
                {
                    break;
                }
            }
        }

        private void BubbleDown(int index)
        {
            int smallestIndex;

            while (true)
            {
                var leftChildIndex = 2 * index + 1;
                var rightChildIndex = 2 * index + 2;
                smallestIndex = index;

                if (leftChildIndex < Count && Compare(leftChildIndex, smallestIndex))
                {
                    smallestIndex = leftChildIndex;
                }

                if (rightChildIndex < Count && Compare(rightChildIndex, smallestIndex))
                {
                    smallestIndex = rightChildIndex;
                }

                if (smallestIndex == index)
                {
                    break;
                }

                Swap(index, smallestIndex);
                index = smallestIndex;
            }
        }

        private bool Compare(int leftIndex, int rightIndex) =>
            Comparer.Compare(heap[leftIndex].Priority, heap[rightIndex].Priority) < 0;

        private void Swap(int leftIndex, int rightIndex)
        {
            (heap[leftIndex], heap[rightIndex]) = (heap[rightIndex], heap[leftIndex]);

            itemIndices[heap[leftIndex].Element] = leftIndex;
            itemIndices[heap[rightIndex].Element] = rightIndex;
        }
    }
}

PriorityQueue.cs

namespace CR.MyPriorityQueue
{
    internal interface PriorityQueue<TElement, TPriority>
    {
        void Enqueue(TElement element, TPriority priority);
        bool Dequeue(out TElement element, out TPriority priority);
    }
}

Program.cs

using CR.PriorityQueues;

class Program
{
    private static readonly int ENQUEUE_ITERATIONS = 1_000_000;

    static void Main(string[] args)
    {
        int seed = (int)Millis();

        Console.WriteLine("Seed = {0}.", seed);

        Random r1 = new Random(seed);
        Random r2 = new Random(seed);

        List<(int, int)> list1 = new List<(int, int)>(ENQUEUE_ITERATIONS);
        List<(int, int)> list2 = new List<(int, int)>(ENQUEUE_ITERATIONS);

        var q1 = new MyPriorityQueue<int, int>();
        var q2 = new CoderoddeBinaryHeap<int, int>();

        long durationMyPriorityQueue = 0;
        long durationCoderoddeBinaryHeap = 0;
        long start = Millis();

        for (int i = 0; i < ENQUEUE_ITERATIONS; i++)
        {
            q1.Enqueue(r1.Next(ENQUEUE_ITERATIONS / 2), r1.Next(ENQUEUE_ITERATIONS));
        }

        long end = Millis();
        durationMyPriorityQueue += end - start;

        Console.WriteLine("{0}.Enqueue() in {1} milliseconds.", q1.GetType().Name, end - start);

        start = Millis();

        while (true)
        {
            bool hasMore = q1.Dequeue(out int key, out int priority);

            if (!hasMore)
            {
                break;
            }

            list1.Add((key, priority));
        }

        end = Millis();
        durationMyPriorityQueue += end - start;

        Console.WriteLine("{0}.TryDequeue() in {1} milliseconds.", q1.GetType().Name, end - start);
        Console.WriteLine("Total {0} duration: {1} milliseconds.", q1.GetType().Name, durationMyPriorityQueue);
        Console.WriteLine();

        start = Millis();

        for (int i = 0; i < ENQUEUE_ITERATIONS; i++)
        {
            q2.Enqueue(r2.Next(ENQUEUE_ITERATIONS / 2), r2.Next(ENQUEUE_ITERATIONS));
        }

        end = Millis();
        durationCoderoddeBinaryHeap += end - start;

        Console.WriteLine("{0}.Enqueue() in {1} milliseconds.", q2.GetType().Name, end - start);

        start = Millis();

        while (true)
        {
            bool hasMore = q2.Dequeue(out int key, out int priority);

            if (!hasMore)
            {
                break;
            }

            list2.Add((key, priority));
        }

        end = Millis();
        durationCoderoddeBinaryHeap += end - start;

        Console.WriteLine("{0}.TryDequeue() in {1} milliseconds.", q2.GetType().Name, end - start);
        Console.WriteLine("Total {0} duration: {1} milliseconds.", q2.GetType().Name, durationCoderoddeBinaryHeap);

        Console.WriteLine();
        Console.WriteLine("Algorithms agree: {0}.", list1.SequenceEqual(list2));
        Console.WriteLine();

        Console.WriteLine("{0} is sorted: {1}.", q1.GetType().Name, IsSorted(list1));
        Console.WriteLine("{0} is sorted: {1}.", q2.GetType().Name, IsSorted(list2));
    }

    private static long Millis()
    {
        return DateTimeOffset.Now.ToUnixTimeMilliseconds();
    }

    private static bool IsSorted(List<(int, int)> list)
    {
        for (int i = 0; i < list.Count - 1; i++)
        {
            if (list[i].Item2 > list[i + 1].Item2)
            {
                return false;
            }
        }

        return true;
    }
}