diff options
| author | Toby Vincent <tobyv13@gmail.com> | 2021-03-25 00:39:48 +0000 |
|---|---|---|
| committer | Toby Vincent <tobyv13@gmail.com> | 2021-03-25 00:39:48 +0000 |
| commit | 960dc370960a97a7bebb113cf73d89e168cd6f3e (patch) | |
| tree | 819fb101aefed7ef9cd61bf1cd71902311e56ebe /PriorityQueue.cs | |
refactored project layout
Diffstat (limited to 'PriorityQueue.cs')
| -rwxr-xr-x | PriorityQueue.cs | 90 |
1 files changed, 90 insertions, 0 deletions
diff --git a/PriorityQueue.cs b/PriorityQueue.cs new file mode 100755 index 0000000..d708f58 --- /dev/null +++ b/PriorityQueue.cs @@ -0,0 +1,90 @@ +using System;
+using PriorityQueue.Interfaces;
+
+namespace PriorityQueue
+{
+ public class PriorityQueue<T, U> : Heap<T, U> where T : INode<U> where U : IComparable<U>
+ {
+ static readonly U _maxValue = (U)typeof(U).GetField("MaxValue").GetValue(null);
+ static readonly U _minValue = (U)typeof(U).GetField("MinValue").GetValue(null);
+
+ public U LeastSignificant { get => IsMin ? _maxValue : _minValue; }
+ public int[] Location { get; set; }
+
+ // indexer
+ public T this[int i] { get => Array[Location[i]]; }
+
+ public PriorityQueue(int size, bool isMin = false)
+ : this(new T[size], isMin) { }
+
+ public PriorityQueue(T[] array, bool isMin = false)
+ : base(array, isMin)
+ {
+ Location = new int[Array.Length];
+ for (int i = 0; i < HeapSize; i++)
+ Location[Array[i].Id] = i;
+ }
+
+ // swap two indexies
+ public new void Swap(int first, int second)
+ {
+ // swap in heap
+ base.Swap(first, second);
+
+ // swap in location table
+ Location[Array[first].Id] = first;
+ Location[Array[second].Id] = second;
+ }
+
+ public void Insert(T node)
+ {
+ int index = ++HeapSize;
+ U key = node.Key;
+
+ node.Key = LeastSignificant;
+ Array[index] = node;
+ Location[node.Id] = index;
+ ChangeKey(index, key);
+ }
+
+ public T Peek() =>
+ Array[0];
+
+ public bool IsEmpty() =>
+ HeapSize < 0;
+
+ // remove and return top node
+ public T Extract()
+ {
+ if (HeapSize < 0)
+ throw new System.OverflowException("Heap Underflow");
+
+ T sig = Peek();
+
+ Swap(0, HeapSize--);
+ Heapify(0);
+
+ return sig;
+ }
+
+ protected bool IsMoreSignificant(U that, U other) =>
+ that.CompareTo(other) * (IsMin ? -1 : 1) > 0;
+
+ public void ChangeKey(int id, U key)
+ {
+ int index = Location[id];
+
+ // key <= Array[index].Key
+ if (!IsMoreSignificant(key, Array[index].Key))
+ throw new System.ArgumentException($"New key ({key}) is less significant than node {id}'s current key ({Array[index].Key}).");
+
+ Array[index].Key = key;
+
+ while (index > 0 && IsMoreSignificant(Array[index], Array[Parent(index)]))
+ {
+ Swap(index, Parent(index));
+ index = Parent(index);
+ }
+ }
+ }
+}
\ No newline at end of file |