Last active
April 18, 2024 07:58
-
-
Save coderodde/5df03dc69ebee96b5f4aa6f6aef2130b to your computer and use it in GitHub Desktop.
An efficient binary heap for C#.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace CR.MyPriorityQueue | |
{ | |
internal interface PriorityQueue<TElement, TPriority> | |
{ | |
void Enqueue(TElement element, TPriority priority); | |
bool Dequeue(out TElement element, out TPriority priority); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment