堆的定义
堆是一种特殊的完全二叉树，它满足一个关键特性：
每个父节点的值都大于或等于其子节点的值。 这意味着在堆的数组表示中，最大的元素总是位于根节点。
这种堆被称为最大堆（Max Heap）。而如果每个父节点的值都小于或等于其子节点，那么这样的堆就是最小堆（Min Heap）。
在本文中，我们将重点讨论最大堆。
如何维护最大堆的特性？
当一个子节点的值大于其父节点，这就违反了最大堆的特性。此时，我们需要交换这两个节点。
如果一个节点的左右子树都是最大堆，但该节点的值小于其子节点，该如何操作？
例如，节点 i 的左右子树都是最大堆，但节点 i 的值小于其子节点。为了解决这个问题，我们可以让节点 i 在堆中“逐级下降”，直至找到合适的位置。
将上述的“逐级下降”过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里是我为维护最大堆特性编写的函数 MAXHEAPIFY，以供参考。
最后，让我们深入思考一个问题：
面对一个随机数组，如果左右子树都不满足最大堆特性，如何将其转化为最大堆？
这不仅是理论上的问题，也是很多算法，如堆排序的基础。期待你的深入思考和实现！
如何建立最大堆
面对一个随机数组，如何将其转化为最大堆？
我们可以从完全二叉树中的最后一个父节点开始，自底向上地使用维护堆特性的 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 函数，我们可以有效地将任意数组转化为最大堆。
在下篇文章中，我们将进一步探讨如何利用最大堆。
WWH 系列文章列表：
[1] Why - 为什么 JS 更像一门编译型语言？
[2] What - 什么是依赖注入？
[3] What - 什么是 Big O？
[4] How - 不同的语言都如何处理错误？
[5] How - 面向对象语言如何处理异常？
[6] Why - 为什么排序算法复杂度上限是 O(NlogN)？
最近文章列表：
[1] 成就卓越：事业成功的核心要素
[2] C++异常处理的底层机制
[3] .git 目录里到底包含了什么？
[4] 看图聊算法：一个游戏让你理解二分法的本质
[5] 看图聊算法：超越二分法，探索大厂经典面试题
[6] 看图聊算法：插入排序，使用频率最高的排序算法
[7] 看图聊算法：归并排序的原理与优化
[8] 看图聊算法：冯·诺依曼的第一个计算机程序
[9] 看图聊算法：快速排序为什么快？
[10] 不刷题，不面试，来看看算法学习在编程世界中的真正价值
[11] 看图聊算法：完全二叉树