-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPriorityQueue.java
More file actions
78 lines (66 loc) · 1.38 KB
/
PriorityQueue.java
File metadata and controls
78 lines (66 loc) · 1.38 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
package com.algs;
public class PriorityQueue<Key extends Comparable<Key>>
{
private static final int DEFAULT_LENGTH = 1 << 4;
private Key[] pq;
private int N = 0;
public PriorityQueue()
{
this(DEFAULT_LENGTH);
}
@SuppressWarnings("unchecked")
public PriorityQueue(int max)
{
pq = (Key[]) new Comparable[max + 1];
}
public boolean isEmpty()
{
return N == 0;
}
public int size()
{
return N;
}
public void insert(Key v)
{
pq[++N] = v;
swin(N);
}
public Key delMax()
{
Key max = pq[1];
exch(1, N--);
pq[N + 1] = null; // 防止对象游离
sink(1);
return max;
}
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;
}
private void swin(int k)
{
while (k > 1 && less(k / 2, k))
{
exch(k / 2, k);
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;
}
}
}