看图聊算法：堆排序，我们学习它可能并不是为了排序

原创 dingtingli dingtingli

2024年01月04日 09:00

在众多排序算法中，堆排序占据了一个独特的位置。与其他排序算法直接进入排序动作不同，堆排序要求我们先与一些基础的数据结构概念打好交道。

这里有完全二叉树，有最大堆，它们不仅构成了堆排序的基础，还引领我们进入了一个更深层次的理解。

你可能会问，既然堆排序并非最快的排序方法，为何还要投入大量时间去学习它？

答案在于，当我们探讨堆排序时，实际上是在探索一个更广泛的应用领域。这不仅仅关于排序本身，还涉及到优先队列等多种实用场景。

因此，让我们踏上这段探索之旅，深入堆排序背后的世界，发现它的真正魅力，远不止于简单的排序功能。

1. 完全二叉树

二叉树（Binary Tree）是一种特殊的数据结构。在这种结构中，每个节点都有两个子节点，通常被称为“左子树”和“右子树”。

二叉树

在这种数据结构中，每个节点都有指向其父节点、左右子节点的三个指针。

当一棵二叉树的特性满足以下条件时，它被称为完全二叉树（Complete Binary Tree）：

除最底层外，其他层的节点数均已满。
最底层的节点都集中在左侧。

完全二叉树

与普通的二叉树不同，完全二叉树可以使用数组进行隐式表示，无需使用指针。

这种表示方法是将树上的所有节点按顺序存放在数组中。节点间的关系可以通过其在数组中的位置来确定。

完全二叉树数组结构

例如，根节点存放在数组的第 1 位置，其左右子节点分别位于 2 和 3 位置。对于任意位置 i 的节点，其父节点和子节点的位置可以通过以下公式计算：

  Parent = i / 2
  Left = 2 * i
  Right = 2 * i + 1

其中，Parent 表示节点 i 的父节点位置，Left 和 Right 分别表示其左子节点和右子节点的位置。

完全二叉树数组节点公式

以图中的数组为例，当 i=4 时，我们可以直接计算出其父节点和两个子节点的位置。

完全二叉树数组节点 i=4

2. 堆

堆是一种特殊的完全二叉树，它满足一个关键特性：

每个父节点的值都大于或等于其子节点的值。 这意味着在堆的数组表示中，最大的元素总是位于根节点。

最大堆

这种堆被称为最大堆（Max Heap）。而如果每个父节点的值都小于或等于其子节点，那么这样的堆就是最小堆（Min Heap）。

在本文中，我们将重点讨论最大堆。

如何维护最大堆的特性？

当一个子节点的值大于其父节点，这就违反了最大堆的特性。此时，我们需要交换这两个节点。

动图节点交换

如果一个节点的左右子树都是最大堆，但该节点的值小于其子节点，该如何操作？

例如，节点 i 的左右子树都是最大堆，但节点 i 的值小于其子节点。为了解决这个问题，我们可以让节点 i 在堆中“逐级下降”，直至找到合适的位置。

动图堆中节点逐级下降

将上述的“逐级下降”过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里是我为维护最大堆特性编写的函数 MAXHEAPIFY，以供参考。

你可以在我的 github 仓库中查看源代码：

https://github.com/dingtingli/algorithm/blob/main/Code/heapsort01.py

最后，让我们深入思考一个问题：

面对一个随机数组，如果左右子树都不满足最大堆特性，如何将其转化为最大堆？

3. 如何建立最大堆

面对一个随机数组，如何将其转化为最大堆？

我们可以从完全二叉树中的最后一个父节点开始，自底向上地使用维护堆特性的 MAXHEAPIFY 函数，从而将任意排序的数组转换成最大堆。

为了实现这个思路，首先需要确定完全二叉树的最后一个父节点。回顾我们之前提到的位置 i 父节点和字节的计算公式:

  Parent = i / 2
  Left = 2 * i
  Right = 2 * i + 1

当节点 i = n/2 时，其左子节点为 left = 2 * (n/2) = n，而 n 即数组中的最后一个元素。

因此，完全二叉树的最后一个父节点的位置为 n/2。

完全二叉树的最后一个父节点

接下来，我们从最后一个父节点开始，自底向上地对每个父节点调用维护堆特性的 MAXHEAPIFY 函数。这样，我们可以逐步将任意排序的数组转换为满足最大堆特性的数组。

动图建立最大堆

如何将这个过程转化为代码呢？你可以先尝试自己实现，然后再参考下面的函数：

def BUILDMAXHEAP(a):
    n = len(a)
    i = n // 2

    # 从最后一个父节点开始，自底向上维护堆特性
    while i >= 1:
        MAXHEAPIFY(a, i, n)
        i -= 1

你可以在我的 github 仓库中查看源代码：

https://github.com/dingtingli/algorithm/blob/main/Code/heapsort01.py

这次，我们学习了如何从一个随机数组构建最大堆。通过自底向上的方法和调用维护堆特性的 MAXHEAPIFY 函数，我们可以有效地将任意数组转化为最大堆。

在下一章节，我们将进一步探讨如何利用最大堆。

4. 堆排序算法

我们已经成功地实现了建立最大堆的 BUILDMAXHEAP 函数，这为我们提供了一个有效的方法将任意数组转化为最大堆。

回顾最大堆的核心特性：每个父节点的值都大于或等于其子节点的值。这确保了在堆的数组表示中，最大的元素始终位于根节点。

最大堆示意图

现在，我们将利用这个特性和 BUILDMAXHEAP 函数来实现排序。

建立最大堆： 使用 BUILDMAXHEAP 函数将任意数组转化为最大堆。
找到最大元素并交换： 最大的元素始终位于数组的第一个位置，将数组的第一个元素与最后一个元素交换。
重建最大堆： 排除最后一个元素，并在剩余的元素中重新构建最大堆。

动图重建最大堆示意图

重复上述过程： 继续交换、排除和重建，直到堆的大小为 2。

因为对于只有两个节点的堆，我们可以直接通过 MAXHEAPIFY 函数完成排序，再进一步交换即可完成排序。

动图堆排序过程示意图

如何将上述过程转化为代码呢？以下是我为堆排序编写的函数，你可以先尝试自己实现，然后再参考：

def HEAPSORT(a):
    # Step 1: Build a max heap
    BUILDMAXHEAP(a)

    n = len(a)
    while n >= 2:
        # Step 2: Swap the first and last element
        exch(a, 1, n)
        n -= 1
        # Step 3: Rebuild the max heap
        MAXHEAPIFY(a, 1, n)