数据结构（五）：堆
本文已参与「新人创作礼」活动，一起开启掘金创作之路。
前言
在数据结构（四）：二叉树中，树是通过链式结构来实现的。在本文中，堆将通过顺序结构实现。同样是树，为什么实现时存储方式不同呢？堆又有哪些特殊的性质呢？
需要注意，本文介绍的堆和操作系统虚拟进程地址空间中的不同，前者是一种数据结构，后者是操作系统中管理内存的一块区域分段。
一、堆
如果有一个数据的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。且满足以下性质：
（1）每个节点的值总是不大于或不小于其父节点的值；
（2）是一棵完全二叉树。
那么这就是一个堆。
如果根节点的值是堆中最小的值，那么这是一个小根堆（大堆）。 如果根节点的值是堆中最大的值，那么这是一个大根堆（小堆）。
二、顺序存储
顺序结构存储就是使用数组来存储，一般只适合表示完全二叉树，因为如果不是完全二叉树，存储时会有空间的浪费。由于堆实际上是一棵完全二叉树，所以堆可以使用数组来存储。
顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
由图中可以看出，左侧一棵完全二叉树存储进一个数组时不存在空间浪费；而右侧非完全二叉树在存储时下标为3、6、7、8的位置没有数据，造成了空间的浪费。
三、堆的实现
堆的结构如下：
```c typedef int HPData;
typedef struct Heap { HPData* a; int size;//当前堆中数据个数 int capacity;//最大容量 }HP; ``` 可以看到，堆的物理结构实际上是一个可动态增长的数组。
1.建堆
下面给出一个数组，逻辑上看作一个堆，现在把它调整成大堆。
c
int a[] = { 15, 18, 28, 34, 65, 19, 49, 25, 37, 27 };
调整的思路：从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点，就可以把整棵树调整成堆。
下面以上图为例进行调整：
（1）倒数第一个非叶子结点：65，左右子树的值都比它小（忽略空），不需要调整。
（2）倒数第二个非叶子结点：34，左子树的值比它小，右子树的值比它大，交换它与右子树的值。（新的堆如下）
以37为根节点的堆是大堆，继续找前一个非叶子节点。
（3）倒数第三个非叶子结点：28，左子树的值比它小，右子树的值比它大，交换它与右子树的值。（新的堆如下）
以49为根节点的堆是大堆，继续找前一个非叶子节点。
（4）倒数第四个非叶子结点：18，左右子树的值都比它大，这时选取左右子树中大的那个值与它交换，即交换它与右子树的值。（新的树如下，注意这时不是堆）
这时以18为根节点的堆显然不是大堆，所以需对这个结点再调整，调整逻辑同上。（新的堆如下）
（5）倒数第五个非叶子结点：15（访问到根结点，调整完根结点后结束），左子右树的值都比它大，这时选取左右子树中大的那个值与它交换，即交换它与左子树的值。（新的堆如下）
此时以15位根的子树不是大堆，按照上述逻辑继续调整。（最终的堆如下）
已经访问到根结点并将根结点调整完毕，调整结束。此时这个堆已经是一个大堆。
上面的调整方法叫做向下调整算法。
但是向下调整算法有一个前提：左右子树必须已经是一个堆，才能调整。
所以必须从倒数第一个非叶子结点开始调整，当调整到前面的非叶子结点时，由于它后面的非叶子结点都已经是大堆，所以这个结点的左右子树也都是大堆，就可以继续使用向下调整算法了。
代码中还用到完全二叉树的一个规律 （根结点是0时成立） ：如果一个结点的下标为n，那么它的左孩子的下标为（2 * n +1），右孩子的下标为（2 * n +2），父结点的下标（n - 1）/ 2。
代码如下（示例）： ```c //交换a、b的值 void Swap(HPData a, HPData b) { HPData temp = a; a = b; b = temp; }
//建大堆 void AdjustDown(HPData* a, int n, int parent) { int child = parent * 2 + 1;//找到左孩子的下标 while (child < n)//调整某一个结点的所有子树，直到符合要求 { //这里注意要先判断child+1是否越界 if (child + 1 < n && a[child + 1] > a[child])//如果右孩子的值大于左孩子，child指向右孩子的下标 child++;
//如果child结点的值比parent结点的值大，就交换数值，并更新child和parent结点继续向下调整
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
//如果child结点的值比parent结点的值小，说明已经是大堆，循环结束
else
break;
}
}
//将一个数组建堆，n为数组的大小 void HeapInit(HP php, HPData a, int n) { assert(php);
php->a = (data*)malloc(sizeof(data)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
php->size = n;
php->capacity = n;
memcpy(php->a, a, sizeof(data)*n);//把数组a中的内容拷贝到php的动态增长的数组中
int i = 0;
//从倒数第一个非叶子结点开始调整
//php->size - 1是最后一个结点的下标；(php->size - 1 - 1) / 2是这个结点的父结点也就是倒数第一个非叶子结点
for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
AdjustDown(php->a, php->size, i);//从最后一个非叶子节点开始依次向上调整
} ```
2.向堆中插入数据
向堆中插入数据时，不能简单的在php->a的末尾加上一个数据，必须要保证插入这个数据后的树仍是一个堆。
这里要用到向上调整算法。就是找到插入数据后最后一个数据的父结点，判断是否符合大堆的特征，如果不符合，交换。重复这一过程直到访问到根结点或者父结点的值大于孩子结点。
以上面的向下调整算法建好的堆为例演示插入数据：
（1）插入的数据40的父结点是27，40大于27，所以以27为根结点的子树不是大堆，交换27和40。（结果如下）
（2）继续向上调整，40的父结点是37，40大于37，所以以37为根结点的子树不是大堆，交换37和40。（结果如下）
（3）继续向上调整，发现此时已经访问到根结点，而且根所在的树已经是大堆，调整完毕。
代码如下（示例）： ```c //向上调整 void AdjustUp(int* a, int child) { if (child <= 0) return;
int parent = (child - 1) / 2;//找到父结点
if (parent >= 0 && a[parent] < a[child])//父结点不越界且不符合大堆就交换
{
Swap(&a[parent], &a[child]);
child = parent;
AdjustUp(a, child);//更新child，递归调整
}
else
return;
}
//向堆中插入数据 void HeapPush(HP* php, HPData x) { assert(php);
if (php->size == php->capacity)//数据满就扩容
{
HPData* tmp = (HPData*)realloc(php->a, php->capacity * 2 * sizeof(HPData));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
//把x插入到php->a的末尾
php->a[php->size] = x;
php->size++;
//向上调整变成堆
AdjustUp(php->a, php->size - 1);
} ```
3.删除堆顶的数据
最简单的思路是把php->a中的数据从第二个开始整体前移一位，然后再向下调整，但是这样实现起来挪动数据需要时间，由于堆被打乱重新调堆又需要时间，时间复杂度太高。
这里采用一种巧妙的思路：交换堆中第一个和最后一个数据，再让php->size减一，这就相当于删除了第一个数据（因为size减一后已经访问不到了），之后再对堆进行向下调整即可。这种思路不需要挪动数据，同时整个树中只有根节点可能不是堆，剩下的子树都仍是堆。时间复杂度很低。
```c //删除堆顶数据（最大的数据） void HeapPop(HP* php) { assert(php); assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);//交换堆中第一个和最后一个数据
php->size--;
AdjustDown(php->a, php->size, 0);//对根进行向下调整
} ```
4.其他对堆的操作
下面的函数实现时较简单，此处不再赘述。
代码如下（示例）：
```c //得到堆顶数据 HPData HeapTop(HP* php) { assert(php); assert(php->size > 0);
return php->a[0];
}
//得到堆中数据的个数 int HeapSize(HP* php) { assert(php); return php->size; }
//判断堆是否为空 bool HeapEmpty(HP* php) { assert(php); return (php->size == 0); }
//堆的销毁 void HeapDestroy(HP* php) { assert(php); free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
free(php);
} ```
四、堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
上图中数组初始时为：2 14 9 10 8 3 1 4 7 5 16
如果简单的建小堆如下
此时的数组为：1 4 2 5 7 3 9 10 14 8 16，而这显然不是升序。 所以排升序要建大堆 每次将堆顶的元素（当前堆中的最大值）与堆中最后一个元素进行交换，接着对剩余的元素调堆（不包含末尾的堆顶元素）。即可得到升序的排列。
```c void HeapSort(int* a, int n) { int i = 0; //初始化堆，建大堆 for (i = (n - 1 - 1) / 2; i >= 0; i--) AjustDown(a, n, i);
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);//交换堆顶元素(即a[0])与堆中的最后一个元素
AjustDown(a, end, 0);//调堆使其成为一个大堆
//注意上面的end一直减少，也就是说堆中的数据个数是越来越少的，被换到后面的数据都是当前堆中最大的数
//仍无序的数都在堆中
end--;
}
} ``` 堆排序：
- 堆排序使用堆来选数，效率就高了很多
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定