书接上文，上篇博客中我说明了堆的定义，那么这一篇就谈谈堆的用法。由于堆快速的增删特性，所以往往有以下重要用途：
- 实现优先队列，用于启发式搜索等内容。
- 一般用于贪心算法中辅助的数据结构。
堆的使用
堆固然好用，但是也要清楚如何使用。
快速手写堆
库固然好用，但是某些情况下你却可能不得不手写堆，那么这时候掌握快速手写堆的技巧便显得尤为重要。
数组是“万能的”，所以一般仅需要一个数组，便能够表示一个堆。众所周知，我们的堆是使用完全二叉树表示的，如下所示：
最小堆.png
我们可以发现，可以将二叉树依次对应到数组中：
可以发现，某个节点的根，实际上就是该节点下标的一半【这也是上个博客实现堆的时候使用的具体原理】。
知道了数组与完全二叉树的对应关系，那么便有可以自己实现最小堆，代码如下：
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
| #include <stdio.h>
#define MAX_N 10000
int heap[MAX_N], sz = 0;
void push(int x) {
int i = sz++;
while (i > 0) {
int p = (i-1) / 2;
if (heap[p] <= x) break;
heap[i] = heap[p];
i = p;
}
heap[i] = x;
}
int pop() {
int ret = heap[0];
int x = heap[--sz];
int i = 0;
while (i*2 + 1 < sz) {
int a = i*2 + 1, b = i*2 + 2;
if (b < sz && heap[b] < heap[a]) a = b;
if (heap[a] > x) break;
heap[i] = heap[a];
i = a;
}
heap[i] = x;
return ret;
}
|
但实际上，很多时候，我们都无需手写，直接调用库即可。
C++ 中的堆
在 <algorithm> 头文件之中，有着堆的模板，有 make_heap() 这样的函数来帮忙建一个堆。但是在实际问题中更为常用的反而是优先队列，优先队列位于 <queue> 头文件中，一段演示代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pque;
pque.push(3);
pque.push(5);
pque.push(1);
while (!pque.empty()) {
cout<<pque.top()<<endl;
pque.pop();
}
return 0;
}
|
- 唯一需要注意的，就是优先队列每次弹出的都是最大的元素，也就是实质上是个最大堆
Java 中的堆
java 中当然也有 堆 和 优先队列，其中优先队列演示代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
System.out.println(pq.peek());
pq.poll();
}
}
|
堆的应用
有这样一道例题：poj 2431，这道题便可以利用优先队列求解：
- 首先将加油站到终点的距离转化为起点到加油站的距离
- 然后，可以抛去实际来看待问题，我们可以采用贪心的思想，一直等到车完全没油之后再加油；而加油时候，选取前面已将路过的加油站中油量最大的油桶【此处可用优先队列节省时间】即可。
AC代码如下：
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
| #include <stdio.h>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int L, P, N;
struct _pair{
int a;
int b;
};
bool cmp(const _pair& left, const _pair& right) {
return left.a < right.a;
}
int main() {
~scanf("%d", &N);
_pair *t = new _pair[N+1];
for (int i = N-1; i >= 0; i--) {
scanf("%d%d", &t[i].a, &t[i].b);
}
scanf("%d%d", &L, &P);
for (int i = 0; i < N; ++i) {
t[i].a = L - t[i].a;
}
sort(t, t+N, cmp);
t[N].a = L;
t[N].b = 0;
N++;
priority_queue<int> que;
int ret = 0, pos = 0, tank = P;
for (int i = 0; i < N; i++) {
int d = t[i].a - pos;
while (tank - d < 0) {
if (que.empty()) {
puts("-1");
return 0;
}
tank += que.top();
que.pop();
ret++;
}
tank -= d;
pos = t[i].a;
que.push(t[i].b);
}
printf("%d\n", ret);
return 0;
}
|
引用
