书接上文,上篇博客中我说明了堆的定义,那么这一篇就谈谈堆的用法。由于堆快速的增删特性,所以往往有以下重要用途:
- 实现优先队列,用于启发式搜索等内容。
- 一般用于贪心算法中辅助的数据结构。
堆的使用
堆固然好用,但是也要清楚如何使用。
快速手写堆
库固然好用,但是某些情况下你却可能不得不手写堆,那么这时候掌握快速手写堆的技巧便显得尤为重要。
数组是“万能的”,所以一般仅需要一个数组,便能够表示一个堆。众所周知,我们的堆是使用完全二叉树表示的,如下所示:
最小堆.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; }
|
引用