Return to Revisions

Advice I - where TPriority : notnull

I would add where TPriority : notnull to the class declaraction, since the priority keys are always required.

Note I

I like your hack:

BubbleUp(index);
BubbleDown(index);

At most one of the two above calls will actually bubble up or down. By the way, it is conventional to call BubbleX as SiftX.

Advice II - performance

You could squeeze some CPU cycles by relying on an array of heap nodes, each heap node containing the item, priority and the index of the item, instead of a List.

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

(The entire benchmark program is in my gist.)

Typical output

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.