leetcode/PriorityQueue.java at master · actor168/leetcode · GitHub

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

publicclassPriorityQueue {

/**
 * 优先级队列：用于共享计算机系统中的作业调度
 * 主要方法：
 * （1）Insert
 * （2）Maximum
 * （3）Extract-Max
 * （4）Increase-Key
 */
privateintLEN = 0;

privateint[] arr;

publicPriorityQueue(int[] a) {
if (a.length > 0 ) {
arr = a;
LEN = arr.length;
 } else {
arr = newint[8];
 }

 }

publicintlength() {
returnLEN;
 }

publicbooleaninsert(intvalue) {
if (arr.length == LEN) {
int[] arr_tmp = newint[ 2 * arr.length ];
intpos = 0;
for (intvar : arr) {
arr_tmp[pos++] = var;
 }
arr = arr_tmp;
 }
if (LEN == 0) {
arr[0] = value;
 } else {
inttmp = arr[0];
arr[0] = value;
arr[LEN] = tmp;

adjust(arr, 0);
 }
LEN++;
returntrue;
 }

publicintmaximum() {
returnarr[0];
 }

publicintextractMax() {
if (this.LEN <= 0) {
return -1;
 }
intmax = arr[0];
arr[0] = arr[LEN-1];
LEN--;
adjust(arr, 0);
returnmax;
 }

publicbooleanincreaseKey(intpos, intvalue) {
if ( pos > LEN ) {
returnfalse;
 }
arr[pos] = value;
intparent = pos / 2;
while ( (pos != parent) && (arr[pos] > arr [parent])) {
inttmp = arr[pos];
arr[pos] = arr[parent];
arr[parent] = tmp;
pos = parent;
parent = parent /2;
 }
returntrue;
 }

privatevoidadjust(int[] arr, intpos) {

intleft = 2 * pos + 1;
intright = 2 * (pos + 1);

intlarge = pos;

if (left < LEN && arr[left] > arr[pos]) {
large = left;
 }

if (right < LEN && arr[right] > arr[large]) {
large = right;
 }

if (large != pos) {
inttmp = arr[large];
arr[large] = arr[pos];
arr[pos] = tmp;
adjust(arr, large);
 }
 }

publicstaticvoidmain(String[] args) {
int[] a = {};
PriorityQueuequeue = newPriorityQueue(a);
queue.insert(8);
queue.insert(5);
queue.insert(4);
queue.increaseKey(2, 10);
System.out.println(queue.extractMax());
System.out.println(queue.maximum());
 }
}