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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
| import java.util.Arrays;
/**
* 二叉堆 这里数据类型为Integer, 且堆为小顶堆
* 几个重要的性质(具有完全二叉树的性质):
* (1).父亲节点的下标为i,则左孩子节点下标2*i+1, 右孩子节点下标2*i+2;同理,下标为i的节点的父亲节点下标为(i-1)/2;
* (2).n个节点的二叉堆,非叶子节点的数目为floor(n/2),如7个节点,则有3个非叶子节点;
* (3).高度为h的完全二叉树,包含2^h到2^(h+1)-1个节点,即n个节点的二叉堆,高度为logn
*
* @Author: baoqiu.xiao@qunar.com Date: 14-7-17 Time: 下午3:45
* @Version: \$Id$
*/
public class PQueue {
/**
* 默认大小
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* 数据
*/
private transient Integer[] queue;
/**
* 大小
*/
private int size = 0;
/**
* ctor
*/
public PQueue() {
this(DEFAULT_CAPACITY);
}
public PQueue(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Integer[initialCapacity];
}
public PQueue(Integer[] array) {
this(array.length);
queue = Arrays.copyOf(array, array.length);
size = array.length;
heapify();
}
/**
* 堆内元素个数, O(1)
*
* @return
*/
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 取堆顶元素(这里为最小元素),但不移除堆顶元素, O(1)
*
* @return
*/
public Integer peek() {
if (size == 0)
return null;
return queue[0];
}
/**
* 弹出堆顶元素并返回, O(logn)
*
* @return
*/
public Integer pop() {
if (size == 0)
return null;
Integer result = queue[0];
queue[0] = queue[--size]; // 数组尾部元素放到堆顶
queue[size] = null;
if (size > 0) {
shiftDown(0);
}
return result;
}
/**
* 往堆里面插入一个元素, O(logn)
*
* @param newValue
*/
public boolean add(Integer newValue) {
if (newValue == null)
throw new NullPointerException();
// 需要增长内存
int oldSize = size;
if (oldSize >= queue.length) {
grow(oldSize + 1);
}
size = oldSize + 1;
queue[oldSize] = newValue;
if (oldSize > 0) {
shiftUp(oldSize);
}
return true;
}
/**
* 内存增长,保证能容纳 minCapacity 个元素
*
* @param minCapacity
*/
private void grow(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
// 这里成倍增长
int oldCapacity = queue.length;
int newCapacity = oldCapacity << 1;
// 校验
if (newCapacity < 0)
newCapacity = Integer.MAX_VALUE;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// 数据拷贝
queue = Arrays.copyOf(this.queue, newCapacity);
}
/**
* 将数组最小堆化 从最后一个非叶子节点,依次往前调整,使得每个子树都满足堆的性质
* 根据下标为i的节点的父亲节点下标为(i-1)/2, 最大下标为size-1, 因此非根节点的最大下标为(size-2)/2, 即size/2 -1
*
* 直观是O(nlogn), 记得算法导论分析的均摊时间应该是O(n), 忘了怎么分析的
*/
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
shiftDown(i);
}
/**
* 向下调整下标为index的节点为根节点的子树, 使其满足堆的性质
* 父亲节点的下标为i,则左孩子节点下标2*i+1, 右孩子节点下标2*i+2
* O(logn)
*
* @param index
*/
private void shiftDown(int index) {
//到达叶子节点了
if(index > ((size >>> 1) - 1) )
return;
//左右孩子中较小的节点candidate
int left = (index << 1) + 1, right = left + 1;
int candidate = left;
if(right < size && queue[right] < queue[left]){
candidate = right;
}
//父节点大于子节点, 则交换父子节点, 并递归调整candide为根节点的子树
if (queue[index] > queue[candidate]) {
swap(index, candidate);
shiftDown(candidate);
}
}
/**
* 向上调整下标为index的节点的数据, 保证其到根节点的路径上都满足堆的性质
* 节点下标为i, 则父节点下标为(i-1)/2
* O(logn)
*
* @param index
*/
private void shiftUp(int index) {
//达到根节点了
if(index <= 0)
return;
int parent = (index-1)>>>1;
//父亲节点 > 当前节点,需要交换
if(parent >= 0 && queue[parent] > queue[index]) {
swap(parent, index);
shiftUp(parent);
}
}
/**
* 交换数组中 i 和 j 的元素
*
* @param i
* @param j
*/
private void swap(int i, int j) {
Integer tmp = queue[i];
queue[i] = queue[j];
queue[j] = tmp;
}
public static void main(String[] args) {
PQueue queue = new PQueue();
queue.add(6);
queue.add(8);
queue.add(2);
queue.add(4);
queue.add(5);
queue.add(7);
queue.add(1);
while (!queue.isEmpty()) {
System.out.println(queue.pop()); //1 2 4 5 6 7 8
}
}
}
|