Introduction

堆，heap。实际上是一个完全二叉树。

完全二叉树：除了最后一层，其余层的节点都达到了最大值。每个节点都向下延伸出两个子节点，最后一层可以没有延伸完全，前面1 ~ n - 1层的子节点都已经延伸完全

堆的基本操作：

  1. 插入一个数
  2. 求集合中的最小值
  3. 删除最小值

用这种方法来模拟，我们还可以额外实现：

  1. 删除任意一个元素
  2. 修改任意一个元素

Train of Thought

我们采用一种数组模拟小根堆的方式来实现堆的操作

小根堆：一个较小的节点向下延伸出两个较大的节点。每个节点都小于等于他的两个子节点

我们从数组下标为1的位置开始，存放根节点。每个节点延伸出两个子节点，我们可以想到：x节点，用2x和2x + 1来存储他的两个子节点

1的子节点：2and3

2的子节点：4and5，3的子节点：6and7

以此类推。

确定了这种模拟方式，我们可以实现各种堆的操作

Pesudo Code

定义一个数组h[]用来存储堆，下标从1开始使用。

注：下标一定要从1开始才能实现我们设想的子节点存储方式！！！

我们先引入一个size变量用来记录当前最后一个节点所在的数组下标

还需要两个函数，upanddown，用来移动堆中的元素

up函数

up函数传入一个节点的数组下标，用来将一个节点向上移动，移动到不能再移动为止。

如果我把一个节点的值减小了，则它有可能向上移动。我们定义一个up函数来进行向上移动，目的是找到它合理的位置，来确保是小根堆

down函数

down同理，将一个增大过值的节点，向下移动，找到合理的位置

插入一个数

堆：完全二叉树。最后一行可能有空缺，也可以是满的。无论哪种情况，直接在数组末尾加一个元素即可

// 设需要加入的值为x
h[++ size] = x;
// 由于刚刚在末尾加入了节点，那么一定是在最后一层。需要进行一个up操作来移动到合理的位置
up(size);
// up操作的参数是需要移动的节点的数组下标

求堆中的最小值

已经确定是小根堆，根节点就是堆中的最小值，但是不一定是唯一的最小值

h[1];

删除最小值

也就是删除根节点，总节点数会减少。但是在这里我们无法直接删除一个节点，因为它还延伸出子节点。我们可以给根节点赋值一个其他值来删除其内容。

对于一列排队的士兵，我们不能直接枪毙第一个，要不然后面的士兵会看到。但是我们可以直接枪毙最后面的，因为没有人会看到。我们想杀第一个，可以把第一个挪到最后一个，同时把最后一个挪到第一个，弥补空缺。然后把最后一个位置上的士兵枪毙即可

h[1] = h[size];
// 把根节点的值换成最后一个节点的值
size --;
// 总节点数减少一个，相当于删除了最后一个节点
down(1);
// 根节点值已经改变，需要找一个合理的位置

删除任意一个元素

同理，把数组下标为k的节点的值改成最后一个节点的值，总数减一，调整位置

h[k] = h[size];
size --;
// 改变k的值，要么这个节点向下移动，要么向上移动，但是我们不知道它到底是向上还是向下
// 所以我们调用两个函数up和down，但是不用担心他会增加时间，因为up和down只会执行一个，让他自行判断即可
up(k);
down(k);

修改任意一个元素

h[k] = x;
up(k);
down(k);

至此，我们设想出了所有的功能，但是还没有代码实现两个重要函数：up和down。下面开始实现

Function Code

down 函数

给定一个节点的数组下标u，则可以获取到两个子节点，三个数比较大小，即行交换即可

void down (int u) {
    int t = u;
    // t为三者的最小值
    if (u * 2 <= size && h[u * 2] < h[u]) t = u * 2;
    // 判断子节点存在，并且，子节点的数值小于爹节点
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[u]) t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
        // 因为一次down只交换一次位置，所以需要递归调换，直到u == t则不再交换
    }
}

构建堆

给定一个数组，构建成堆

这里有很高级的复杂度分析！！！
朴素方法

直接使用上面的插入函数，遍历数组，对每个元素都执行一遍插入元素，使其堆化

显然，这种方法时间复杂度比较高，我们可以进行分析：

$$ \begin{align} &输入一个新的元素x，位于最下层，执行up函数调整位置\\ &不妨设一共有N个元素，则一共有log_{2}N层，up执行log_{2}N次\\ &一共N个元素，总时间复杂度等于相乘，即O(Nlog_{2}N) \end{align} $$

这里分析其实本来写的是小写n，但是发现小写n可能会被当成对数的底数，于是改成大写N了

数学知识告诉我们，$ O(Nlog_{2}N) > O(N) $。我们还有一种时间复杂度为$O(N)$的堆化方式：

在给定的数组上，直接进行修改。即直接执行upanddown函数。

我们分析一下如何执行up和down能有最小的时间复杂度

首先我们有结论：设堆一共有节点n个，则n/2是最后一个有子节点的节点的下标

例如，一共有4个节点，则4/2 = 2，第2个节点是最后一个有子节点的节点，第3and4个节点都没有子节点。一共有5个节点，则5/2 = 2，第2个节点是最后一个有子节点的节点，第3and4and5个节点都没有子节点。

得出结论：无论有奇数还是偶数个节点，n / 2都是最后一个有子节点的节点的下标。如果n为偶数，则说明，最后一个有子节点的节点有一个子节点。如果n为奇数，则说明，最后一个有子节点的节点有两个子节点。同时可以证明，如果n从偶数加一，变成奇数，最后一个有子节点的节点的下标不会改变：只是最后一个有子节点的节点增加了一个子节点，并不是让下一个节点也从零到一新增了一个子节点

另外，我们还可以知道堆的某层元素个数有结论：

一个堆中有n个元素，则最后一层的元素个数为$\frac n 2$。

注：此处的元素个数均指相应数量级，且，我们不妨设，该堆已经形成满二叉树。例如n = 7时，最后一层为4个元素。n = 99时，最后一层为50个元素。普遍规律为$\frac {n+1} {2}$。为了方便计算，我们可以将其用$\frac n 2$表示。

前方高能！！！

最底层有$\frac n 2$个元素，倒数第二层有$\frac n 4$个元素，倒数第三层有$\frac n 8$个元素……以此类推，每向上一层，元素个数变为一半

最底层不用动，我们从倒数第二层开始建堆：这$\frac n 4$个元素向下移动一层，则时间复杂度为$\frac n 4 * 1$

倒数第三层：$\frac n 8$个元素，向下移动两层，则时间复杂度为$\frac n 8 * 2$

我们得到了总时间复杂度的表达式：

$$ \begin{align} \frac n 4 * 1 + \frac n 8 * 2 + \frac n {16} * 3 + ... + \frac n {2^{k+1}} * k + ... \end{align} $$

我们把$n$提出来。显然这是一个数列求和，等差乘等比：错位相减

$$ \begin{align} S &= \frac 1 {2^2} + \frac 2 {2^3} + \frac 3 {2^4} + \frac 4 {2^5} + ... \\ 2S &= \frac 1 {2^1} + \frac 2 {2^2} + \frac 3 {2^3} + \frac 4 {2^4} + ... \\ &两式左右分别相减，可以得到 \\ S &= \frac 1 2 + \frac 1 {2^2} + \frac 1 {2^3} + \frac 1 {2^4} + ... \\ &显然这样一个式子是收敛的 \\ &即P级数在底数大于1时收敛小于1 \\ &所以总时间复杂度小于O(n) \end{align} $$

所以我们构建堆的代码非常简单：

for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
// 把数据读入数组h
// h是需要堆化的数组
for (int i = n / 2; i; i -- ) down(i);
// 从最后一个有子节点的节点开始执行down
// 一定要从下往上执行！！！不可以反顺序

up函数

down函数需要跟两个子节点比较，但是up函数只需要跟一个爹节点比较，所以会比较简单。

注：数组模拟堆中，下标表示的堆节点的位置是永远不变的，所有的操作都是改变节点的值

void up (int u ) {
    while (u / 2 && h[u / 2] > h[u]) { // 判断存在父节点，并且，父节点比当前节点大
        swap(h[u / 2], h[u]);
        u /= 2;
        // 交换值之后，判断爹节点
    }
}
最后修改：2022 年 11 月 14 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏