packagecom.tiger.study.DataStructure.PriorithQueue;publicclassMaxPriorityQueue<TextendsComparable<T>>{privateT[] items;privateintN;// 构造方法publicMaxPriorityQueue(int capacity){this.items =(T[])newComparable[capacity +1];this.N=0;}// 比较i位置和j位置元素的大小privatebooleanless(int i,int j){return items[i].compareTo(items[j])<0;}// 交换i位置和j位置的元素privatevoidexch(int i,int j){T tmp = items[i];
items[i]= items[j];
items[j]= tmp;}// 删除队列中最大的元素并返回这个最大的元素publicTdelMax(){T max = items[1];exch(1,N);N--;sink(1);return max;}// 往队列中插入一个元素publicvoidinsert(T t){
items[++N]= t;swim(N);}// 使用上浮算法,使索引k处的元素在堆中处于一个正确的位置privatevoidswim(int k){while(k >1){if(less(k /2, k)){exch(k /2, k);}
k = k /2;}}// 使用下沉算法,使索引k处元素在堆中处于一个正确的位置privatevoidsink(int k){while(2* k <=N){int max;if(2* k +1<=N){
max = items[2* k].compareTo(items[2* k +1])>0?2* k:2* k +1;}else{
max =2* k;}if(items[k].compareTo(items[max])<0){exch(k, max);}else{break;}
k = max;}}// 返回优先队列的大小publicintsize(){returnthis.N;}// 判断优先队列是否为空publicbooleanisEmpty(){returnthis.N==0;}}
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
1.3 最小优先队列
之前堆中存放数据元素的数组需要满足以下特性:
最大的元素放在数组的索引1处
每个结点的数据总是大于等于它的两个子节点的数据。
最小优先队列可以使用相反的思想来实现。
1.3.1 最小优先队列的代码实现
1.3.2 代码实现
packagecom.tiger.study.DataStructure.PriorithQueue;publicclassMinPriorityQueue<TextendsComparable<T>>{privateT[] items;privateintN;publicMinPriorityQueue(int capacity){this.items =(T[])newComparable[capacity +1];this.N=0;}privatebooleanless(int i,int j){return items[i].compareTo(items[j])<0;}privatevoidexch(int i,int j){T tmp = items[i];
items[i]= items[j];
items[j]= tmp;}publicTdelMin(){T min = items[1];exch(1,N);N--;sink(1);return min;}publicvoidinsert(T t){
items[++N]= t;swim(N);}publicvoidswim(int k){while(k >1){if(!less(k /2, k)){exch(k /2, k);}
k = k /2;}}publicvoidsink(int k){int min;while(2* k <N){if(2* k +1<N){if(less(2* k,2* k +1)){
min =2* k;}else{
min =2* k +1;}}else{
min =2* k;}if(less(k, min)){break;}exch(k, min);
k = min;}}publicintsize(){returnN;}publicbooleanisEmpty(){returnN==0;}}
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
1.4 索引优先队列
1.4.1 索引优先队列实现思路
存储数据时,给每个数据元素关联一个整数,例如:insert(int k, T t),我们可以看作k是t关联的整数,那么我们实现需要通过k这个值,快速获取到对垒中t这个元素,此时又k这个值需要有唯一性。最直观的想法就是我们可以用一个T[] items数组来保存数据元素,在insert(int k, T t)完成插入时,可以把k看做事items数组的索引,把t元素放到items数组的索引k处,这样我们在根据k获取元素t时就很方便了,直接可以哪到items[k]即可;