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.
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;
}
}
(The entire benchmark program is in my gist.)
Typical output
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.
Hope that helps.
