数据结构之最小堆

最小堆可以看作是一种优先级队列的实现，有些应用场景需要从队列中获取最小的或者最大的元素，而且不要求数据全部有序，使用最小堆或者最大堆能很好的解决这类问题。

最小堆的元素是按完全二叉树的顺序存储方式存放在一维数组中。

蓝色数字代表节点元素在数组中的索引位置

如上图所示，最小堆的根节点对应数组的第一个元素，后面接着依次从上到下每一层树节点从左往右排列，按照这个顺序将一段线性内存结构映射为一个树结构，并且满足下面的几个性质：

用i代表数组下标，n表示数组大小

• 当i为0时，表示树的根节点，没有父节点;
• 节点i对应的左子节点为2i + 1，右子节点为2i + 2，父节点为(i - 1) / 2;
• 当2i + 1 > n - 1时，则节点i无左子节点;
• 当2i + 2 > n - 1时，则节点i无右子节点；

数组作为二叉树的存储方式，可以快速的定位父节点和左右子节点，也更加节省内存。

如下给出一组数据，并展示如何将这组数据转换成一个最小堆。

最小堆的转换从最后一个非叶子节点开始，逐个将每个子树转换成一个最小堆，直到根节点也转换完成，则整棵树变成了一个最小堆。

首先找出最后一个非叶子节点，此节点必然是最后一个节点的父节点。

最后一个节点为n - 1，它的父节点为((n-1)-1) / 2，即：（n - 2）/ 2，对于上面的例子，则为节点3。

从节点3开始将节点3为根节点的子树转换成一个最小堆，依次处理2，1，0节点；

下面为转换过程：

节点3转换

节点3只有一个左子节点，节点3小于节点7，节点3所在的子树是一个最小堆，不需要转换。

节点2转换

节点2有左右两个子节点，节点5小于节点6，让节点2和节点5比较，由于节点2大于节点5，交换两个节点元素，得到的以节点2为根节点的子树成为一个最小堆。

节点1转换

节点1存在左右节点，其中节点4小于节点3，所以，节点1和节点4比较，由于节点1大于节点4，交换节点1和节点4元素。

节点0转换

节点0存在左右节点，其中右节点小于左节点，所以节点0和右节点比较，由于节点0大于节点2，所以交换两个节点的元素，交换之后，节点2所在的子树需要再做比较判断，节点5小于节点6，所以节点2和节点5比较，由于节点2大于节点5，交换节点2和节点5元素，至此，整个转换结束，最终得到一个最小堆。

代码实现：

int heap[] = {24, 22, 17, 23, 5, 4, 67, 68};
int n = sizeof(heap) / sizeof(int);
int lastIndex = n - 1;
int starIndex = (n - 2) / 2;
for(int i = starIndex; i >= 0; --i){	// 循环进行将每个子树都转换成一个最小堆
    int root = i; 						// 子树根节点
    int temp = heap[i];
    int j = 2 * root + 1;				// 左子节点
    while(j <= lastIndex){
        if(j < lastIndex && heap[j] > heap[j  + 1]) j++;	// 找到左右节点中较小的一个节点位置
        if(temp <= heap[j]) break; 		// 如果根节点值小于左右子节点，则退出比较循环
        else{
            heap[root] = heap[j]; 		// 小的值上移
            root = j;					// 将下面的节点作为一个根节点继续比较
            j = 2 * root + 1;			// 重新计算左子节点位置
        }
    }
    heap[root] = temp;
}  ```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20