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 /Heap.cs | |
refactored project layout
Diffstat (limited to 'Heap.cs')
| -rwxr-xr-x | Heap.cs | 73 |
1 files changed, 73 insertions, 0 deletions
@@ -0,0 +1,73 @@ +using System;
+using PriorityQueue.Interfaces;
+
+namespace PriorityQueue
+{
+ public class Heap<T, U> where T : INode<U> where U : IComparable<U>
+ {
+ public T[] Array { get; set; }
+ protected int HeapSize { get; set; } = -1;
+ protected bool IsMin { get; set; }
+
+ public Heap(int size = 20, bool isMin = false)
+ : this(new T[size], isMin) { }
+
+ public Heap(T[] array, bool isMin = false)
+ {
+ Array = array;
+ IsMin = isMin;
+ }
+
+
+ // get node's parent
+ protected int Parent(int index) =>
+ (index - 1) / 2;
+
+ // get node's left child
+ protected int Left(int index) =>
+ 2 * index + 1;
+
+ // get node's right child
+ protected int Right(int index) =>
+ 2 * index + 1;
+
+ // swap two indexies
+ protected void Swap(int that, int other)
+ {
+ // swap in heap
+ T temp = Array[that];
+ Array[that] = Array[other];
+ Array[other] = temp;
+ }
+
+ protected bool IsMoreSignificant(T that, T other) =>
+ that.CompareTo(other) * (IsMin ? -1 : 1) > 0;
+
+ // build local heap
+ protected void Heapify(int index)
+ {
+ int sig = index;
+ int left = 2 * index + 1;
+ int right = 2 * index + 2;
+
+ if (left <= HeapSize && IsMoreSignificant(Array[left], Array[sig]))
+ sig = left;
+
+ if (right <= HeapSize && IsMoreSignificant(Array[right], Array[sig]))
+ sig = right;
+
+ if (sig != index)
+ {
+ Swap(index, sig);
+ Heapify(sig);
+ }
+ }
+
+ // build local heap for each node
+ protected void BuildHeap()
+ {
+ for (int i = HeapSize / 2; i >= 0; i--)
+ Heapify(i);
+ }
+ }
+}
\ No newline at end of file |