diff options
Diffstat (limited to 'Heap.cs')
-rw-r--r--[-rwxr-xr-x] | Heap.cs | 140 |
1 files changed, 70 insertions, 70 deletions
@@ -1,71 +1,71 @@ -using System;
-using 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 + 2;
-
- // swap two indexies
- protected virtual void Swap(int that, int other)
- {
- // swap in heap
- T temp = Array[that];
- Array[that] = Array[other];
- Array[other] = temp;
- }
-
- public bool MoreSignificant(T that, T other) =>
- that.CompareTo(other) * (IsMin ? -1 : 1) > 0;
-
- // build local heap
- protected void Heapify(int index)
- {
- int sig = index;
-
- if (Left(index) <= HeapSize && MoreSignificant(Array[Left(index)], Array[sig]))
- sig = Left(index);
-
- if (Right(index) <= HeapSize && MoreSignificant(Array[Right(index)], Array[sig]))
- sig = Right(index);
-
- 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);
- }
- }
+using System; +using 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 + 2; + + // swap two indexies + protected virtual void Swap(int that, int other) + { + // swap in heap + T temp = Array[that]; + Array[that] = Array[other]; + Array[other] = temp; + } + + public bool MoreSignificant(T that, T other) => + that.CompareTo(other) * (IsMin ? -1 : 1) > 0; + + // build local heap + protected void Heapify(int index) + { + int sig = index; + + if (Left(index) <= HeapSize && MoreSignificant(Array[Left(index)], Array[sig])) + sig = Left(index); + + if (Right(index) <= HeapSize && MoreSignificant(Array[Right(index)], Array[sig])) + sig = Right(index); + + 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 |