Java 使用最大堆实现优先级队列。堆大小固定，并使用数组表示。
使用最大堆实现优先级队列。堆大小固定，并使用数组表示。
实例源码：
源代码：
执行
执行中...
x
1
2
3
import java.util.Arrays;/** from 时 代 J a v a 公 众 号 - nowjava.com**/4
5
6
public class PriorityQueue {7
8
int[] heap;9
10
int size;11
12
13
// Constructor initializes instance variables14
15
public PriorityQueue(int maxSize) {16
17
heap = new int[maxSize];18
19
size = 0;20
21
}22
23
24
// Push an element on to the queue25
26
public void push(int val) {27
28
// If the queue is full then throw an exception29
30
if (size == heap.length)31
32
throw new IllegalStateException();33
34
35
// Put the value in the next available space in the queue36
37
int pos = size;38
39
heap[pos] = val;/*来 自 n o w j a v a . c o m*/40
41
42
// While val is bigger than its parent, swap it with its parent43
44
while (pos > 0) {45
46
// Get the parent and compare the values47
48
int parent = (pos + 1) / 2 - 1;49
50
if (heap[parent] >= heap[pos])51
52
break;53
54
swapIndices(parent, pos);55
56
pos = parent;57
58
}59
60
61
// We added an element so increment the size62
63
size++;64
65
}66
67
68
// Pop the max element from the queue69
70
public int pop() {71
72
// If the queue is empty, throw an exception73
74
if (size == 0)75
76
throw new IllegalStateException();77
78
79
// The top of the heap is the first item in the array, so save it off80
81
// to the side so we don't lose it82
83
int toReturn = heap[0];84
85
86
// Move the bottom item in the heap to the first position. We don't need87
88
// to remove it from the array because we have the size variable89
90
heap[0] = heap[size - 1];91
92
size--;93
94
95
// Bubble down the top element to the right spot96
97
int pos = 0;98
99
// We're going to be swapping with the children and any pos >= size / 2100
101
// doesn't have any children102
103
while (pos < size / 2) {104
105
int leftChild = pos * 2 + 1;106
107
int rightChild = leftChild + 1;108
109
// If the right child exists and is greater than the left child, 110
111
// compare it to the current position112
113
if (rightChild < size && heap[leftChild] < heap[rightChild]) {114
115
// Only swap if the value is less than the child116
117
if (heap[pos] >= heap[rightChild])118
119
break;120
121
swapIndices(pos, rightChild);122
123
pos = rightChild;124
125
} else {126
127
// Do the same comparison with the left child128
129
if (heap[pos] >= heap[leftChild])130
131
break;132
133
swapIndices(pos, leftChild);134
135
pos = leftChild;136
137
}138
139
}140
141
142
return toReturn;143
144
}145
146
147
// Swap the values at the indices148
149
private void swapIndices(int i, int j) {150
151
int temp = heap[i];152
153
heap[i] = heap[j];154
155
heap[j] = temp;156
157
}158
159
160
public static void main(String[] args) {161
162
tester(new int[] {}, "Empty");163
164
tester(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 }, "Ascending order");165
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java