-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxPQ.java
More file actions
82 lines (78 loc) · 1.76 KB
/
Copy pathMaxPQ.java
File metadata and controls
82 lines (78 loc) · 1.76 KB
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
/**
* Created by mofma on 2016/12/16.
*/
public class MaxPQ<Key extends Comparable<Key>>
{
private Key[] pq;
private int N;
public MaxPQ(int capacity)
{
pq = (Key[]) new Comparable[capacity+1];
N =0;
}
public boolean isEmpty()
{ return N == 0; }
public int getSize()
{
return N;
}
public Key getMax()
{ return pq[1]; }
public void insert(Key key)
{
pq[++N] = key;
swim(N);
}
public Key delMax()
{
Key max = pq[1];
exch(1,N--);
sink(1);
pq[N+1] = null;
return max;
}
private void swim(int k)
{
while(k>1 && less(k/2,k)) {
exch(k,k/2);
k = k/2;
}
}
private void sink(int k)
{
while(2*k <= N) {
int j = 2*k;
if(j<N && less(j,j+1)) j++;
if(!less(k,j)) break;
exch(k,j);
k = j;
}
}
private boolean less(int i, int j)
{
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j)
{
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
public static void main(String[] args)
{
MaxPQ<Character> testMaxPQ = new MaxPQ<Character> (128);
testMaxPQ.insert('P');
testMaxPQ.insert('A');
testMaxPQ.insert('D');
testMaxPQ.insert('S');
testMaxPQ.insert('Z');
testMaxPQ.insert('R');
testMaxPQ.insert('M');
testMaxPQ.insert('N');
System.out.printf("N=%d, max=%c\n",testMaxPQ.getSize(),testMaxPQ.getMax());
testMaxPQ.delMax();
testMaxPQ.delMax();
testMaxPQ.insert('H');
System.out.printf("N=%d, max=%c\n",testMaxPQ.getSize(),testMaxPQ.getMax());
}
}