谭浩的博客

Simple is beauty.

堆及堆的应用

基本介绍

堆是一种基于树的数据结构。其满足以下特征:给定堆的中任意节点 P 和 C, 若 P 是 C 的父节点,那么 P 的值小于等于(或大于等于)C 的值。如果父节点的值恒小于子节点的值,则为最小堆,反之则为最大堆。

因为堆所具有的这种特性,因此其常为另一种抽象数据结构(优先队列)的最高效的实现方式。在堆中最高或者最低权限的元素总是存储在根节点。需要注意的是:堆并不是一个有序的数据结构,其只保证了父节点与子节点之间的有序,因此是部分有序的。

常见操作

以下实现一个二叉堆(小根堆),其常用于堆排序,通过该例子展示堆上的一般操作:

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
import java.util.Arrays;
import java.util.Optional;

public class MinHeap {

private int[] data;
private int size;
private static final int DEFAULT_SIZE = 10;

private MinHeap(){
data = new int[10];
this.size = 0;
}

public MinHeap(int size) {
data = new int[size];
this.size = 0;
}

// 基本操作

/**
* 返回根节点的值
* @return 其值可能为空
*/
public Optional<Integer> peek() {
if (size != 0) {
return Optional.of(data[0]);
}
return Optional.empty();

}

/**
* 向堆中插入新的值
* @param e
*/
public void push(int e) {
if (size == data.length) {
data = Arrays.copyOf(data, size * 2);
}
data[size] = e;
size++;
shiftUp();
}

/**
* 删除堆的根节点
* @return 可能为空
*/
public Optional<Integer> pop() {
if (size == 0) {
return Optional.empty();
} else {
Integer res = data[0];
data[0] = data[size-1];
size--;
shiftDown(0);
return Optional.of(res);
}
}

/**
* 删除堆的根节点,并添加新值。比 pop 之后再 push 更加高效
* @param e
*/
public Optional<Integer> replace(int e) {
if (size == 0) {
push(e);
return Optional.empty();
}
Integer res = data[0];
data[0] = e;
shiftDown(0);
return Optional.of(res);
}

/**
* 传入数组,创建一个最小堆。
* @param arr
* @return
*/
public static MinHeap build(int[] arr) {
MinHeap heap = new MinHeap();
heap.data = arr;
heap.size = arr.length;
for (int i = heap.size/2 - 1; i >=0; i--) {
heap.shiftDown(i);
}
return heap;
}

// 检查堆的状态

/**
* 返回堆的大小
* @return
*/
public int size() {
return size;
}

/**
* 判断堆是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}

// 内部操作
private void shiftUp() {
int k = size - 1;
int p = (k - 1) / 2;
while (k != 0 && data[p] > data[k]) {
data[k] = data[k]^data[p];
data[p] = data[k]^data[p];
data[k] = data[k]^data[p];
k = p;
p = (k - 1) / 2;
}
}

private void shiftDown(int i) {
int l = i * 2 + 1, r = i * 2 + 2, m;
if (l > size - 1) {
return;
}
if (r > size - 1) {
m = l;
} else {
m = data[l] > data[r] ? r : l;
}

if (data[i] > data[m]) {
data[i] = data[i]^data[m];
data[m] = data[i]^data[m];
data[i] = data[i]^data[m];
shiftDown(m);
}

}

public static void main(String[] args) {
MinHeap heap = new MinHeap(10);
heap.push(34);
heap.push(24);
heap.push(54);
heap.push(4);
heap.push(3);
heap.push(14);
heap.push(84);
heap.push(35);
heap.push(34);
heap.push(36);
heap.push(74);
heap.push(32);
heap.push(31);
heap.push(39);
int[] arr = {1,54,23,12,46,78,12,3,6};
MinHeap heap2 = MinHeap.build(arr);

while (!heap.isEmpty()) {
System.out.println(heap.pop().get());
}
System.out.println("=========================");
while (!heap2.isEmpty()) {
System.out.println(heap2.pop().get());
}

}
}

堆的大用途

堆的常用用途就是使用堆来进行排序,又称堆排序【移除根节点,对堆做递归调整】。除了常用于堆排序之外,堆还可以用于解决经典的 TopN 问题。例如考虑以下问题:在一个内存大小为 2GB 的计算机上计算 10 亿个整数中最大的 1000 个整数。

考虑到 10 亿个整数大约需要 40 亿字节的存储空间,大约需要 4GB 的内存空间,所以显然不能考虑对 10 亿个整数排序之后取前 1000 个数的做法。如果不考虑使用堆时,我们可以将数据分成多个文件在进行计算,但这样会增加磁盘的IO次数,导致程序运行效率低下。或者可以使用多台机器,编写 MapReduce 程序在多台机器上分别计算 1000 个最大数据之后做 Reduce 操作,但该方法不符合在一台计算机上解决问题的要求。

对于以上问题,利用小顶堆我们可以更加高效地找出最大的 1000 个数,首先取数据的前 1000 个数在内存中创建一个大小为 1000 的小顶堆。然后依次读取文件中的数据,和小顶堆的堆顶进行比较,如果数据比堆顶还小则直接丢弃该数据,否则替换堆顶数,并调整堆结构。如此,数据文件只需要读取一次,且最终内存中小顶堆的数据就为前 1000 大的数。

利用上面的小顶堆实现伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class TopN {
public static void main(String[] args) {
int[] arr; //前1000个数据
MinHeap heap = MinHeap.build(arr);

while (读取数据m) {
if (m < heap.peek().get()) {
continue
}
heap.replace(m);
}

while (!heap.isEmpty()) {
System.out.println(heap.pop().get());
}

}

}