数据结构（混合式）23-24-1 堆复习笔记

本资料由 @BlockLune 整理，课本为《数据结构（C 语言）第 2 版慕课版》2020 年 2 月第 2 版，2022 年 12 月第 11 次印刷。

注意：

本资料知识点来自于对应的复习 PPT，但具体实现更多参考自 Princeton Algs4、GeeksforGeeks 的内容。这导致文中的实现并不一定与课本实现完全一致。
本资料免费分享于 NJUPTFreeExams，请勿商业使用！如有错别字等错误，请在 Issues 中提出，感谢！

基本概念

堆是一种特殊的基于完全二叉树的数据结构。可分为两种：

最小堆：任意子树的根的元素都是该子树中最小元素的堆
最大堆：…最大…

由于堆是一个完全二叉树，所以常用数组表示。

对于从 0 开始索引的堆，节点 $i$ 的左子节点索引为 $2i+1$ ，右子节点的索引为 $2i+2$ ，父节点的索引为 $(i-1)/2$ （整除）。
…1…，节点 $i$ …左… $2i$ ，右… $2i+1$ ，父… $i/2$ （整除）。

操作

操作	时间复杂度
建堆	$O(n)$
插入	$O(\log n)$
删除	$O(\log n)$
查看堆顶元素	$O(1)$

以下操作以最大堆为例（注意课本是以最小堆为例的），请特别注意最大最小堆不同的调整方法：

上移操作

当子节点的元素值大于其父节点的元素值时，需要进行上移操作（promotion, or swim）。

以下代码是对 algs4 中相应代码的 Python 改写：

def swim(k: int):                                  # k 为开始上移的节点，是一个子节点
    while k > start_index and less(parent(k), k):  # 当前节点 k 没有到达根并且父节点的元素值小于当前节点的元素值时
        exch(k, parent(k))                         # 交换两者的元素值
        k = parent(k)                              # 将当前节点更新为其父节点，以继续进行上移操作

或者看这个与下边的下移操作看上去更为统一的版本：

def swim(k: int):
    while k > start_index:
        if less(k, parent(k)):
            break
        else:
            exch(k, parent(k))
            k = parent(k)

要点：

最大堆中，在当前节点 $k$ 存在父节点（也就是说它是非根节点）时，循环判断当前节点 $k$ 是否小于其父节点的元素值：

如果是，调整完成，退出循环；
如果不是，则交换当前节点 $k$ 与其父节点的元素值，并将 $k$ 更新为其父节点，继续循环。

下移操作

当父节点的元素值小于它的其中一个（或者两个）子节点的元素值时，需要进行下移操作（demotion, or sink）。

以下代码是对 algs4 中相应代码结合课本 AdjustDown代码的 Python 改写：

def sink(k: int, border: int):
    while left(k) <= border:
        larger_is_right_condition = right(k) <= border and less(left(k), right(k))
        larger = right(k) if larger_is_right_condition else left(k)

        if not less(k, larger_child):
            break
        else:
            exch(k, larger)
            k = larger

要点：

最大堆中，在当前节点 $k$ 存在子节点时，循环判断当前节点 $k$ 是否不小于（大于等于）其更大的子节点：

如果是，调整完成，退出循环；
如果不是，交换当前节点 $k$ 与其元素值更大的子节点的元素值，并将 $k$ 更新为那个子节点，继续循环。

在上边的代码实现中，因为存在左节点是存在子节点的必要条件（完全二叉树的性质），所以循环条件设置为了 left(k) <= border，即在限定范围内左节点是否存在，然后再在循环体内判断右节点是否存在及左右节点哪个的元素值更大，最后再判断是否需要调整。

建堆操作

从最后一个非叶节点开始，到根节点，分别执行下移操作。

插入操作

在末尾插入一个节点，然后对它执行上移操作。

删除操作

将末尾的节点与根节点交换，然后对它执行下移操作。

查看堆顶元素

数组支持随机读取，所以直接读第一个元素就好了。

判断是否是一个堆

首先检查给定的内容是否是一棵完全二叉树；
接着检查这棵完全二叉树是不是一个堆，对于最小（最大）堆，检查每个节点的元素值是否小于（大于）以它为根的子树中所有其他节点的元素值。

数据结构（混合式）23-24-1 堆 复习笔记