Return to Answer

Seed = -265595956.
MyPriorityQueue`2.Enqueue() in 607 milliseconds.
MyPriorityQueue`2.TryDequeue() in 1745 milliseconds.
Total MyPriorityQueue`2 duration: 2352 milliseconds.

CoderoddeBinaryHeap`2.Enqueue() in 952 milliseconds.
CoderoddeBinaryHeap`2.TryDequeue() in 441 milliseconds.
Total CoderoddeBinaryHeap`2 duration: 1393 milliseconds.

Algorithms agree: True.

MyPriorityQueue`2 is sorted: True.
CoderoddeBinaryHeap`2 is sorted: True.

Seed = -264809311.
MyPriorityQueue`2.Enqueue() in 625 milliseconds.
MyPriorityQueue`2.TryDequeue() in 1941 milliseconds.
Total MyPriorityQueue`2 duration: 2566 milliseconds.

CoderoddeBinaryHeap`2.Enqueue() in 835 milliseconds.
CoderoddeBinaryHeap`2.TryDequeue() in 450 milliseconds.
Total CoderoddeBinaryHeap`2 duration: 1285 milliseconds.

Algorithms agree: True.

MyPriorityQueue`2 is sorted: True.
CoderoddeBinaryHeap`2 is sorted: True.

Summa summarum

All in all, I had the following rewrite in mind:

namespace CR.PriorityQueues
{
    class CoderoddeBinaryHeap<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 (IsFull())
            {
                ExtendHeapNodeArray();
            }

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

        public void EnqueueOrUpdate(TElement item, TPriority priority)
        {
            if (map.TryGetValue(item, out HeapNode<TElement, TPriority> node))
            {
                node.priority = priority;
                SiftUp(node.index);
                SiftDown(node.index);
            }
            else
            {
                Enqueue(item, priority);
            }
        }

        public bool TryDequeue(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;
            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 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 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 shouldShrink()
        {
            return heapNodeArray.Length / 2 != INITIAL_CAPACITY &&
                4 * size <= heapNodeArray.Length;
        }

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

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

Seed = -368462730.
MyPriorityQueue`2.Enqueue() in 117 milliseconds.
MyPriorityQueue`2.EnqueueOrUpdate() in 474 milliseconds.
MyPriorityQueue`2.TryDequeue() in 2176 milliseconds.
Total MyPriorityQueue`2 duration: 2767 milliseconds.

CoderoddeBinaryHeap`2.Enqueue() in 288 milliseconds.
CoderoddeBinaryHeap`2.EnqueueOrUpdate() in 195 milliseconds.
CoderoddeBinaryHeap`2.TryDequeue() in 1010 milliseconds.
Total CoderoddeBinaryHeap`2 duration: 1493 milliseconds.

Algorithms agree: True.

MyPriorityQueue`2 is sorted: True.
CoderoddeBinaryHeap`2 is sorted: True.

Note II - slight incorretness

If you run the following:

var q = new MyPriorityQueue<int, int>();

q.Enqueue(1, 1);
q.Enqueue(1, 1);
q.EnqueueOrUpdate(1, 0);
q.EnqueueOrUpdate(1, 2);

Console.WriteLine("Size: {0}.", q.Count);

bool b = q.TryDequeue(out int e, out int p);

Console.WriteLine("{0}: {1}, {2}.", b, e, p);
Console.WriteLine("Size: {0}.", q.Count);

b = q.TryDequeue(out e, out p);

Console.WriteLine("{0}: {1}, {2}.", b, e, p);
Console.WriteLine("Size: {0}.", q.Count);

you will get:

Size: 2.
True: 1, 1. <--- Should be "True: 1, 0."
Size: 1.
True: 1, 2.
Size: 0.

Advice III - alternative API

I suggest you rip an interface (call it, for example, PriorityQueue) since there are several priority queue data types: binary heap, \$d\$-ary heap, binomial heap, Fibonacci heap, pairing heap.

The interface in question is:

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

Above, if the element to enqueue does not appear in the queue, it is added. Otherwise, its priority is updated.

Summa summarum

All in all, I had the following rewrite in mind. I start with your rewrite:

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

Next, I will show your what I had in mind:

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

Seed = -265595956.
MyPriorityQueue`2.Enqueue() in 607 milliseconds.
MyPriorityQueue`2.TryDequeue() in 1745 milliseconds.
Total MyPriorityQueue`2 duration: 2352 milliseconds.

CoderoddeBinaryHeap`2.Enqueue() in 952 milliseconds.
CoderoddeBinaryHeap`2.TryDequeue() in 441 milliseconds.
Total CoderoddeBinaryHeap`2 duration: 1393 milliseconds.

Algorithms agree: True.

MyPriorityQueue`2 is sorted: True.
CoderoddeBinaryHeap`2 is sorted: True.

Hope that helps.

namespace CR.PriorityQueues
{
    class CoderoddeBinaryHeap<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 (IsFull())
            {
                extendHeapNodeArray();
            }

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

        public void EnqueueOrUpdate(TElement item, TPriority priority)
        {
            if (map.TryGetValue(item, out HeapNode<TElement, TPriority> node))
            {
                node.priority = priority;
                SiftUp(node.index);
                SiftDown(node.index);
            }
            else
            {
                Enqueue(item, priority);
            }
        }

        public bool TryDequeue(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;
            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 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 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 shouldShrink()
        {
            return heapNodeArray.Length / 2 != INITIAL_CAPACITY &&
                4 * size <= heapNodeArray.Length;
        }

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

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

namespace CR.PriorityQueues
{
    class CoderoddeBinaryHeap<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 (IsFull())
            {
                ExtendHeapNodeArray();
            }

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

        public void EnqueueOrUpdate(TElement item, TPriority priority)
        {
            if (map.TryGetValue(item, out HeapNode<TElement, TPriority> node))
            {
                node.priority = priority;
                SiftUp(node.index);
                SiftDown(node.index);
            }
            else
            {
                Enqueue(item, priority);
            }
        }

        public bool TryDequeue(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;
            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 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 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 shouldShrink()
        {
            return heapNodeArray.Length / 2 != INITIAL_CAPACITY &&
                4 * size <= heapNodeArray.Length;
        }

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

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