-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinaryHeapWithMap.cs
122 lines (101 loc) · 3.41 KB
/
BinaryHeapWithMap.cs
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
namespace rac.so.bytehaven
{
public class BinaryHeapWithMap<T>
{
/* An implementation of the Heap+Map data structure. MIT License.
Made with ♠ by Racso. https://rac.so | https://github.com/Racso */
private readonly int[] priorities;
private readonly T[] data;
private int count;
private readonly Dictionary<T, int> map;
private readonly Func<int, int, int> priorityComparer;
public BinaryHeapWithMap(int capacity, IComparer<int> comparer)
: this(capacity, comparer.Compare)
{
}
public BinaryHeapWithMap(int capacity, Func<int, int, int> priorityComparer)
{
data = new T[capacity];
priorities = new int[capacity];
map = new Dictionary<T, int>(capacity);
this.priorityComparer = priorityComparer;
}
public int Count => count;
public (T Value, int Priority) Peek()
=> (data[0], priorities[0]);
public void Push(T item, int priority)
{
data[count] = item;
priorities[count] = priority;
map[item] = count;
SiftUp(count);
count++;
}
public (T Value, int Priority) Pop()
{
T result = data[0];
int priority = priorities[0];
data[0] = data[count - 1];
priorities[0] = priorities[count - 1];
map[data[0]] = 0;
count--;
map.Remove(result);
SiftDown(0);
return (result, priority);
}
public bool Remove(T item)
{
if (!map.TryGetValue(item, out int index))
return false;
data[index] = data[count - 1];
priorities[index] = priorities[count - 1];
map[data[index]] = index;
count--;
map.Remove(item);
if (index == 0 || priorityComparer(priorities[index], priorities[(index - 1) / 2]) >= 0)
SiftDown(index);
else
SiftUp(index);
return true;
}
public bool Contains(T item)
{
return map.ContainsKey(item);
}
private void SiftUp(int index)
{
while (index > 0)
{
int parent = (index - 1) / 2;
if (priorityComparer(priorities[index], priorities[parent]) >= 0)
break;
Swap(index, parent);
index = parent;
}
}
private void SiftDown(int index)
{
while (true)
{
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
if (left < count && priorityComparer(priorities[left], priorities[smallest]) < 0)
smallest = left;
if (right < count && priorityComparer(priorities[right], priorities[smallest]) < 0)
smallest = right;
if (smallest == index)
break;
Swap(index, smallest);
index = smallest;
}
}
private void Swap(int a, int b)
{
(data[a], data[b]) = (data[b], data[a]);
(priorities[a], priorities[b]) = (priorities[b], priorities[a]);
map[data[a]] = a;
map[data[b]] = b;
}
}
}