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
89
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 int CompareKey(U that, U other) =>
that.CompareTo(other) * (IsMin ? -1 : 1);
public void ChangeKey(int id, U key)
{
int index = Location[id];
// key <= Array[index].Key
if (CompareKey(key, Array[index].Key) < 0)
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 && CompareKey(Array[index], Array[Parent(index)]) > 0)
{
Swap(index, Parent(index));
index = Parent(index);
}
}
}
}
|
