上一篇博客我们讲了一种叫并查集的数据结构，这里我们再讲另外一种数据结构——堆。

　　堆是一种能凸显最重要数据的数据结构（最大值或最小值）。

　　首先，堆是由完全二叉树勾成的。什么是完全二叉树呢？进化到完全体的树状数码宝贝。完全二叉树是指如二叉树的高度为h，除h层外，其他各层（1到h-1层）的结点个数都达到最大，第h层的结点都连续集中分布在最左边。如图：

 

　　同时，通过观察我们还发现对于结点x，它的父亲结点为x/2（若存在）（舍去小数部分），它的左右儿子结点分别为2x，2x+1（若存在）

　　知道了完全二叉树的这两个特性，我们会发现，咦，我完全可以用数组模拟一个完全二叉树。没错，数组确实可以模拟完全二叉树，接下来我们就聊聊堆。

 

　 堆分为大根堆与小根堆。对大根堆来说，对每一个结点都有：它的父亲结点的值比它大，它的儿子结点的值比它小。那么第一个节点存储的值就是整个堆里最大的值了。小根堆的特性与之相反。

　　哦。原来这就是堆。那大根堆里第二个结点就是第二大的元素啦，最后一个结点就最小的元素啦。然而并不是这样，大根堆只是保证对每个结点，它的值大于它的儿子结点的值，小于它的父亲结点得值。也就是说，堆里的元素并不是按升序或降序排列的，堆仅仅是凸显了最重要的元素，使得大根堆的根结点为最大的元素，小根堆的结点为最小的元素。

 

　　下面我们以大根堆为例，看看如何创建一个堆。

　　首先是堆的创建，我们用push函数将一个新元素加入到堆中。

1 #define maxsize 3000000
2 
3 int heap[maxsize];
4 
5 void push(int x) {
6     num++;    //num代表当前堆中的元素数量
7     heap[num] = x;
8     up(num);
9 }

　　　咦，为什么出现了一个奇怪的up函数。我们直接把x放在第num个节点中，但第num个结点不一定遵循堆的特性，为了维护堆的特性，我们必须让x上浮。怎样上浮呢？如果x的值大于它的父亲结点的值，那么就交换它和它的父亲结点，直到它的值小于它的父亲结点或已经是根结点为止。

 1 #define maxsize 3000000
 2 
 3 int heap[maxsize];
 4 
 5 void up(int x) {
 6     while (x/2 > 0) {    //如果x/2<=0,说明x已经是根结点了，不能再上浮了
 7         if (heap[x] > heap[x/2]) {
 8             swap(&heap[x], &heap[x/2]);
 9             x = x / 2;
10         }
11         else {
12             break;
13         }
14     }
15 }

　　这里出现的swap函数是一个简单的交换函数，相信大家都能实现（如果不能实现，建议先学好基础，暂时不学习堆）。

　　学会了怎么把数据读入堆的小茗又犯愁了，我该怎么把根结点从堆中弹出呢？这时候就需要一个pop函数了。

1 #define maxsize 3000000
2 
3 int heap[maxsize];
4 
5 void pop() {
6     heap[1] = heap[num];
7     num--;
8     down(1);
9 }

　　这里我们将最后一个结点的值赋值给根结点，根结点就被覆盖了。同时num--，原来的第num个结点就在范围外了。但原来的num结点不一定是堆中最大的元素，为了维护堆，我们就让这个结点下沉，直到它的值大于它的儿子结点或它没有儿子结点。

 1 #define maxsize 3000000
 2 
 3 int heap[maxsize];
 4 
 5 void down(int x) {
 6     while (x*2 <= num) {
 7         int maxson = 2*x;
 8         if (maxson+1 <= num && heap[maxson+1] > heap[maxson]) {
 9             maxson++;
10         }
11 
12         if (heap[maxson] > heap[x]) {
13             swap(&heap[maxson], &heap[x]);
14             x = maxson;
15         }
16         else {
17             break;
18         }
19     }
20 }

　　这样，我们就基本实现了堆的基本功能，我们就能随时查看堆中最重要的值了。

1 #define maxsize 3000000
2 
3 int heap[maxsize];
4 
5 int gettop() {
6     return heap[1];
7 }

　　怎么样，堆这种数据结构你学废了学会了吗？