【堆】堆的基本概念及操作，堆与优先队列

1. 堆的概念

堆（heap）是一棵特殊的完全二叉树，它满足堆中某个节点的值总是不大于或不小于其父节点的值。而根据这一性质我们可以把堆分为两类：

• 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值。
• 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值

注：大顶堆有时也叫大根堆，小顶堆有时也叫小根堆。

我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。不难发现，对于大顶堆（小顶堆），堆顶元素（根节点）的值总是最大（最小）的。

2. 堆的存储结构

在之前的二叉树学习当中我们知道，完全二叉树非常适合使用数组的形式来表示，因此在计算机的实现当中，堆往往采用一维数组的形式来存储，而数组也是堆的物理结构，上面所说的完全二叉树则是堆的逻辑结构，也就是我们在脑子里所想的结构。那一会儿说堆是完全二叉树，一会儿又是一维数组，那堆到底是线性的还是非线性的呢？

结论：我们判断一个数据结构的类型往往看的是它的逻辑结构。

也就是说堆还是一个非线性的数据结构。只不过在计算机实现中，是采用的数组来表示堆。

如上图所示，如果我们给一个完全二叉树从左到右从上到下依次从 0 开始编号（也可以从 1 开始），那么这些编号可以对应到一个数组中形成一个一维数组的形式，从图中可以看到：

给定索引 $i$ ，其左子节点的索引为 $2i+1$ ，右子节点的索引为 $2i+2$ ，父节点的索引为 $(i-1)/2$（向下整除）。当索引越界时，表示空节点或节点不存在。

3. 堆的结构体定义

// Heap.h
typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;
} Heap;

4. 堆的插入

向上调整算法

当我们向堆中插入数据时，需要使用向上调整算法调整，因为向堆中插入数据是将数据插入到数组中下标为 size 的位置，此时就不一定满足小堆(大堆)，因此，需要堆其进行调整，此处以小堆为例，向上调整法只需从插入的节点位置开始和父节点比较，若 a[child] < a[parent]，则交换，若 a[child] >= a[parent] 则说明已经满足小堆，直接 break 。

// 堆的向上调整算法
// 建小堆
void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;  // 通过下标引索找到父节点while(child > 0){if(a[child] < a[parent]){  // 这里是建小堆，如果父亲比孩子大，则交换int temp = a[parent];  // 这里可以单独在外面写一个Swap函数a[parent] = a[child];a[child] = temp;child = parent;  // 更新下标引索parent = (child - 1) / 2;  // 找到新的父节点然后继续比较}else{break;}}
}

插入操作

接下来我们就可以来进行插入操作了：

void HeapPush(Heap* php, HPDataType x){assert(php);  if (php->size == php->capacity){HPDataType* temp = (HPDataType*)realloc(php->a,php->capacity * 2 * sizeof(HPDataType));if (temp == NULL){printf("realloc fail\n");exit(-1);}php->a = temp;php->capacity *= 2;}php->a[php->size] = x;++php->size;AdjustUp(php->a,php->size - 1);
}

5. 堆的删除

向下调整算法

以下操作以小堆为例

假设我们有一个这样的数组：{15， 3， 4， 7， 6， 5， 9， 10， 12， 8}。通过构建成一棵完全二叉树之后如下：

我们会发现这棵树除了根节点 15 之外它的左右子树都是一个小堆，如果我们希望这一整棵树变成一个小堆的话我们就需要采用向下调整算法，即将这个 15 向下挪动进行调整，从而让这棵树符合堆的特点。

向下调整算法-前提：当前树的左右子树必须都是一个小堆（大堆）

向下调整算法的核心思想：（以建小堆为例）选出左右孩子中小的那一个，跟父亲交换，小的往上浮，大的往下沉，如果要建大堆则相反。

以下是动图演示：

// 向下调整法
// 建小堆
void AdjustDown(HPDataType* a, int n, int root){int parent = root;int child = 2 * parent + 1;while(child < n){// 防止没有右孩子       左右孩子比较if(child + 1 < n && a[child] > a[child + 1]){child++;  // 如果左孩子大，那就要选右孩子，因此++}// 父节点与小的那个孩子比较，如果父节点大，则交换if(a[parent] > a[child]){int temp = a[parent];a[parent] = a[child];a[child] = temp;parent = child;  // 更新下标child = 2 * parent + 1;  // 找到新的孩子然后继续比较}else{break;}}
}

删除操作

现在有了向下调整法，我们便可以来删除堆中的元素了，那么删谁？随便删吗？当然不是，在大堆和小堆中我们都能发现它的根节点一定是堆中最大（大堆）或者是最小（小堆）的，那么在堆中我们也通常只会去删除这一个节点的元素，即——弹出头部元素。

直接删除根节点的话会很麻烦，但是如果是删除最后一个叶子节点（数组中的尾删）的话会很方便，那么我们不妨将根节点与最后一个叶子节点交换，然后尾删，之后再将新的根节点做向下调整即可。

以下是动图演示：

void HeapPop(Heap* php){assert(php);assert(php->size > 0);HPDataType temp = php->a[php->size - 1];php->a[php->size - 1] = php->a[0];php->a[0] = temp;--php->size;AdjustDown(php->a, php->size, 0);
}

注意：此函数不返回被删除的元素。

6. 创建堆

数组建堆算法

上面我们的向下调整算法有个限制条件那就是当前树的左右子树必须都是一个小堆（大堆），那要是左右子树不是小堆（大堆）呢？其实向下调整算法主要可以用于创建一个堆的操作。

比如下面这个二叉树，它现在完全不符合一个堆的特点：

如果我们想要把它建成小堆，则可以从倒数第一个非叶子节点的位置开使用向下调整算法。

如下图所示可以按图中的步骤依次向下调整，如何找到倒数第一个非叶子节点？不难发现，最后一个非叶子节点是最后一个叶子节点的父亲，所以它的小标为 $(n-1-1)/2$ 。（$n-1$ 代表最后一个叶子，再减 $1$ 除以 $2$ 则是它的父亲）

// 数组建堆算法
for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(arr, n, i);
}

复杂度分析

• 假设完全二叉树的节点数量为 $n$ ，则叶节点数量为 $(n+1)/2$ ，其中 / 为向下整除。因此需要堆化的节点数量为 $(n-1)/2$ 。
• 在从顶至底堆化的过程中，每个节点最多堆化到叶节点，因此最大迭代次数为二叉树高度 ${\log }_{2}n$ 。

将上述两者相乘，可得到建堆过程的时间复杂度为 $O(n{\log }_{2}n)$ 。但这个估算结果并不准确，因为我们没有考虑到二叉树底层节点数量远多于顶层节点的性质。

接下来我们来进行更为准确的计算。为了降低计算难度，假设给定一个节点数量为 $n$ 、高度为 $h$ 的 “满二叉树”，该假设不会影响计算结果的正确性。

如图所示，节点 “从顶至底堆化” 的最大迭代次数等于该节点到叶节点的距离，而该距离正是 “节点高度”。因此，我们可以对各层的 “节点数量 × 节点高度” 求和，得到所有节点的堆化迭代次数的总和。
$$T(h)=2^{0}h+2^1(h-1)+2^2(h-2)+\cdots +2^{h-1}\times 1$$
化简上式需要借助中学的数列知识，先将 $T(h)$ 乘以 $2$ ，得到：
$$2T(h)=2^{1}h+2^2(h-1)+2^3(h-2)+\cdots +2^h\times 1$$
使用错位相减法，用下式 $2T(h)$ 减去上式 $T(h)$ ，可得：
$$2T(h)-T(h)=T(h)=-2^{0}h+2^1+2^2+\cdots +2^{h-1}+2^h$$
观察上式，发现 $T(h)$ 是一个等比数列，可直接使用求和公式，得到时间复杂度为：
$$\begin{array}{rl}T(h)& =2\frac{1-2^h}{1-2}-h\\ & =2^{h+1}-h-2\\ & =O(2^h)\end{array}$$
进一步，高度为 $h$ 的满二叉树的节点数量为 $n=2^{h+1}-1$ ，易得复杂度为 $O(2^h)=O(n)$ 。以上推算表明，输入列表并建堆的时间复杂度为 $O(n)$ ，非常高效。

堆的初始化

有了建堆操作之后，给定我们一个随机数组，我们就可以将它进行建堆操作了：

void HeapInit(Heap* php, HPDataType* a, int n){  // php是指向Heap结构体的指针assert(php);assert(a);php->a = (HPDataType*)malloc(n * sizeof(HPDataType)); if (php->a == NULL){printf("malloc fail\n");exit(-1);}for (int i = 0; i < n; i++){php->a[i] = a[i];  // 拷贝数据，也可用库函数}//建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(php->a, n, i);}php->capacity = n;php->size = n;
}

7. 堆的销毁

void HeapDestroy(Heap* php){assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}

8. 获取堆内数据的个数

int HeapSize(Heap* php){assert(php);return php->size;
}

9. 堆的判空

//判断堆是否为空
//为空返回1，不为空返回0
int HeapEmpty(Heap* php){assert(php);return php->size == 0 ? 1 : 0;
}

10. 获取堆顶的数据

HPDataType HeapTop(Heap* php){assert(php);assert(php->size > 0);return php->a[0];
}

11. 堆与优先队列

我们都知道普通的队列，是一种满足先进先出特点的数据结构。

而优先队列与之有点不同，它是一种特殊的队列，在优先队列中，每个元素都有一定的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列可以用于任何需要元素按照一定顺序处理的场景，例如操作系统任务调度、序列合并等。

而这里的优先级就可以看作是队列中数的大小，即在队列中的数据最大（最小）的先出，这刚好和我们所讲的堆的操作十分契合，因此实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将 “优先队列” 和 “堆” 看作等价的数据结构。

12. 堆排序

堆排序详见此处——【堆排序】

13. 完整代码

// Heap.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;typedef struct Heap {HPDataType* a;int size;int capacity;
} Heap;// 向上调整
void AdjustUp(HPDataType* a, int child);
// 向下调整
void AdjustDown(HPDataType* a, int n, int root);
// 堆的初始化
void HeapInit(Heap *php, HPDataType *a, int n);
// 插入元素
void HeapPush(Heap *php, HPDataType x);
// 删除堆顶元素
void HeapPop(Heap *php);
// 堆的销毁
void HeapDestroy(Heap *php);
// 获取堆中数据的个数
int HeapSize(Heap *php);
// 堆的判空
int HeapEmpty(Heap* php);
// 获取堆顶数据
HPDataType HeapTop(Heap *php);

// Heap.c

#include "Heap.h"// 向上调整，以小堆为例
void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;while(child>0){if(a[child] < a[parent]){int temp = a[parent];a[parent] = a[child];a[child] = temp;child = parent;parent = (child - 1) / 2;}else{break;}}
}// 向下调整，以小堆为例
void AdjustDown(HPDataType* a, int n, int root){int parent = root;int child = 2 * parent + 1;while(child < n){// 防止没有右孩子       左右孩子比较if(child + 1 < n && a[child] > a[child + 1]){child++;  // 如果左孩子大，那就要选右孩子，因此++}// 父节点与小的那个孩子比较，如果父节点大，则交换if(a[parent] > a[child]){int temp = a[parent];a[parent] = a[child];a[child] = temp;parent = child;  // 更新下标child = 2 * parent + 1;  // 找到新的孩子然后继续比较}else{break;}}
}// 初始化堆
void HeapInit(Heap* php, HPDataType* a, int n){assert(php);assert(a);php->a = (HPDataType*)malloc(n * sizeof(HPDataType)); if (php->a == NULL){printf("malloc fail\n");exit(-1);}for (int i = 0; i < n; i++){php->a[i] = a[i];  // 拷贝数据，也可用库函数}//建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(php->a, n, i);}php->capacity = n;php->size = n;
}//堆的插入
void HeapPush(Heap* php, HPDataType x){assert(php);  if (php->size == php->capacity){HPDataType* temp = (HPDataType*)realloc(php->a,php->capacity * 2 * sizeof(HPDataType));if (temp == NULL){printf("realloc fail\n");exit(-1);}php->a = temp;php->capacity *= 2;}php->a[php->size] = x;++php->size;AdjustUp(php->a,php->size - 1);
}// 删除堆顶元素
void HeapPop(Heap* php){assert(php);assert(php->size > 0);HPDataType temp = php->a[php->size - 1];php->a[php->size - 1] = php->a[0];php->a[0] = temp;--php->size;AdjustDown(php->a, php->size, 0);
}// 堆的销毁
void HeapDestroy(Heap* php){assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}//堆里的数据个数
int HeapSize(Heap* php){assert(php);return php->size;
}//判断堆是否为空
//为空返回1，不为空返回0
int HeapEmpty(Heap* php){assert(php);return php->size == 0 ? 1 : 0;
}//取堆顶数据
HPDataType HeapTop(Heap* php){assert(php);assert(php->size > 0);return php->a[0];
}

// HeapTest.c

#include "Heap.h"void test1(){int a[] = { 27, 28, 65, 25, 15, 34, 19, 49, 18, 37 };Heap hp;HeapInit(&hp, a, sizeof(a)/sizeof(int));while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}// 15 18 19 25 27 28 34 37 49 65printf("\n");HeapDestroy(&hp);
}
int main(){test1();return 0;
}