跳转至

二叉堆

结构

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不大于儿子的权值（小根堆）。

由堆性质，树根存的是最小值（getmin 操作就解决了）。

插入操作

首先，要保证插入后也是一棵完全二叉树。

最简单的方法就是，最下一层最右边的叶子之后插入。

如果最下一层已满，就新增一层。

插入之后可能会不满足堆性质？

向上调整：如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。

可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。

向上调整的时间复杂度是 O(\log n)的。

删除操作

删除根结点。

如果直接删除，则变成了两个堆，难以处理。

所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。

然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。

于是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质……

向下调整：在该结点的所有儿子中，找一个最小的，与该结点交换，重复此过程直到底层。

可以证明，删除并向下调整后，没有其他结点不满足堆性质。

时间复杂度 O(\log n)。

减小某个点的权值

很显然，直接修改后，向上调整一次即可，时间复杂度为 O(\log n)。

实现

我们发现，上面介绍的几种操作主要依赖于两个核心：向上调整和向下调整。

（伪代码）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
up(x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}
down(x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] < h[t]) t++;
    if (h[t] >= h[x]) break;
    swap(h[x], h[t]);
    x = t;
  }
}

建堆

考虑这么一个问题，从一个空的堆开始，插入 n个元素，不在乎顺序。

直接一个一个插入需要 O(n \log n)的时间，有没有更好的方法？

方法一：使用 decreasekey（即，向上调整）

从根开始，按 BFS 序进行。

1
2
3
build_heap_1() {
    for (i = 1; i <= n; i++) up(i);
}

为啥这么做：对于第 k层的结点，向上调整的复杂度为 O(k)而不是 O(\log n)。

总复杂度： \log 1 + \log 2 + \cdots + \log n = \Theta(n \log n)。

（在「基于比较的排序」中证明过）

方法二：使用向下调整

这时换一种思路，从叶子开始，逐个向下调整

1
2
3
build_heap_2() {
    for (i = n; i >= 1; i--) down(i);
}

换一种理解方法，每次「合并」两个已经调整好的堆，这说明了正确性。

注意到向下调整的复杂度，为 O(\log n - k)。

\begin{aligned} 总复杂度 & = n \log n - \log 1 - \log 2 - \cdots - \log n \\ & \leq n \log n - 0 \times 2^0 - 1 \times 2^1 -\cdots - (\log n - 1) \times \frac{n}{2} \\\ & = n \log n - (n-1) - (n-2) - (n-4) - \cdots - (n-\frac{n}{2}) \\ & = n \log n - n \log n + 1 + 2 + 4 + \cdots + \frac{n}{2} \\ & = n - 1 \\ & = O(n) \end{aligned}

之所以能 O(n)建堆，是因为堆性质很弱，二叉堆并不是唯一的。

要是像排序那样的强条件就难说了。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论