上一篇博客中用到了优先队列，它的内部是用堆实现的，这篇就来回忆一下堆是怎么实现的。
堆是一棵完全二叉树，即
数字0，1，2……代表节点的下标，即一维数组中元素的位置。
第k个节点的左右子节点分别是：
第n个节点的父节点是：
因为堆是一棵完全二叉树，所以插入和删除一个节点，维护的成本都是O(logn)。
如果这是个最小堆，即顶点元素的值最小，
插入时：
将节点插入到数组末尾n，然后与它的父节点m=parent(n)比较，如果值比父节点小，则交换，继续从m向上比较。
删除时：
交换顶点元素heap[0]和末尾元素heap[n]，然后从顶点向下比较，直到父节点比子节点都小结束。
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
| package structure;
public class Heap<E extends Comparable<E>> {
private Object[] heap;
private int size;
public static void main(String[] args) {
int r = 10000000;
long start = System.currentTimeMillis();
test0(r);
long end = System.currentTimeMillis();
System.out.println(end - start);
}
public static void test0(int r) {
Heap<Integer> heap = new Heap<>(r);
for (int i = r; i > 0; i--) {
heap.add(i);
}
System.out.println("length: " + heap.heap.length);
while (heap.isNotEmpty()) {
heap.peak();
}
}
public Heap() {
heap = new Object[32];
size = 0;
}
public Heap(int capacity) {
heap = new Object[capacity];
size = 0;
}
public E peak() {
if (size > 0) {
Object o = heap[0];
heap[0] = heap[size - 1];
size = size - 1;
siftDown(0);
return (E) o;
} else {
return null;
}
}
public void add(E e) {
resizeIfNeed();
heap[size] = e;
size = size + 1;
siftUp(size - 1);
}
public boolean isNotEmpty() {
return size > 0;
}
private void resizeIfNeed() {
if (size == heap.length) {
int capacity = heap.length + (heap.length >> 1);
Object[] extend = new Object[capacity];
System.arraycopy(heap, 0, extend, 0, size);
heap = extend;
}
}
private void siftUp(int i) {
for (int j = parent(i); j >= 0; j = parent(i)) {
if (bigger(j, i)) {
swap(j, i);
i = j;
}
}
}
private void siftDown(int i) {
int ls = leftSon(i), rs = ls + 1;
if (rs < size && bigger(ls, rs)) {
if (bigger(i, rs)) {
swap(i, rs);
siftDown(rs);
}
} else if (ls < size && bigger(i, ls)) {
swap(i, ls);
siftDown(ls);
}
}
private int parent(int i) {
return (i - 1) >> 1;
}
private int leftSon(int i) {
return (i << 1) + 1;
}
private void swap(int i, int j) {
Object o = heap[j];
heap[j] = heap[i];
heap[i] = o;
}
private boolean bigger(int i, int j) {
return ((E) heap[i]).compareTo((E) heap[j]) > 0 ? true : false;
}
}
|
一个int有4个字节，1KB=2^8个int，那 1GB=2^10*2^10*2^8=2^28=268435456(int)，PriorityQueue的最大长度为(Integer.MAX_VALUE-8),即((1<<31)-1)-8=2147483639，看来是我多虑了，2亿的数组其实不算什么，业务量真有那么大，应该会有更好的处理方法。
如果想要Integer.MAX_VALUE*2的数组怎么办，只能用Unsafe去直接内存申请了，这部分内存不受GC影响，不受JVM限制，需要自己释放。一般是不建议使用，即便你觉得它很有用。
