1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
using System;
using Interfaces;
namespace PriorityQueue
{
public class PriorityQueue<T, U> : Heap<T, U> where T : INode<U> where U : IComparable<U>
{
// workaround for due to inablitly to call MaxValue/MinValue on generics
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 - returns null if attempting to access outside heap
public T this[int i] { get => Location[i] > HeapSize ? default(T) : 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];
}
// swap two indexies
protected override 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;
}
// insert a new node and bubble up
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);
}
// return most significant
public T Peek() =>
Array[0];
// check if heap is empty
public bool IsEmpty() =>
HeapSize < 0;
// remove and return top node
public T Extract()
{
if (HeapSize < 0)
throw new System.OverflowException("Heap Underflow");
T head = Peek();
Swap(0, HeapSize--);
Heapify(0);
return head;
}
protected bool LessSignificant(U that, U other) =>
that.CompareTo(other) * (IsMin ? -1 : 1) > 0;
public void ChangeKey(int id, U key)
{
int index = Location[id];
Array[index].Key = key;
while (index > 0 && MoreSignificant(Array[index], Array[Parent(index)]))
{
Swap(index, Parent(index));
index = Parent(index);
}
}
}
}
|