-
Notifications
You must be signed in to change notification settings - Fork 1
/
OrderedArrayMaxPQ.cs
80 lines (64 loc) · 2.13 KB
/
OrderedArrayMaxPQ.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
namespace SedgewickWayne.Algorithms
{
using System;
/// <summary>
/// Priority queue implementation with an ordered array.
/// </summary>
/// <remarks>
/// Limitations:
/// - no array resizing.
/// - does not check for overflow or underflow.
/// </remarks>
public class OrderedArrayMaxPQ<TKey>
: ArrayPQBase<TKey>
, IMaxPriorityQueue<TKey>
where TKey : IComparable<TKey>
{
public OrderedArrayMaxPQ(int capacity = 0) : base(capacity)
{
}
public override ArrayPQBase<TKey> Clone()
{
var clone = new OrderedArrayMaxPQ<TKey>(this.pq.Length);
clone.n = this.n;
clone.pq = this.pq;
return clone;
}
public override TKey Top => pq[n];
public TKey Max => throw new NotImplementedException();
/// <summary>
/// the code for remove the maximum in the priority queue is the same as for pop in the stack.
/// </summary>
/// <returns></returns>
public override TKey Delete()
{
// half capacity if less than quarter
if ((n > 0) && (n == pq.Length / 4)) resize(pq.Length / 2);
return pq[--n];
}
/// <summary>
/// move larger entries one position to the right,
/// thus keeping the entries in the array in order (as in insertion sort).
/// Thus the largest item is always at the end.
/// </summary>
/// <param name="key"></param>
public override void Insert(TKey key)
{
// double size of array if necessary
if (n == 0) resize(4);
else if (n == pq.Length) resize(2 * pq.Length);
int i = n - 1;
while (i >= 0 && predicate(key, pq[i]))
{
pq[i + 1] = pq[i];
i--;
}
pq[i + 1] = key;
n++;
}
bool predicate(TKey v, TKey w) => v.CompareTo(w) < 0;
public override bool ComparePredicate(int i, int j) => pq[i].CompareTo(pq[j]) < 0;
public TKey DeleteMax() => Delete();
}
}