上一篇文章中介绍了完全二叉树，这次我们来了解一种特殊的完全二叉树，堆。看图聊算法：完全二叉树

堆的定义

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

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

最大堆

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

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

如何维护最大堆的特性？

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

动图 节点交换

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

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

动图 堆中节点逐级下降

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

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

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

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

这不仅是理论上的问题，也是很多算法，如堆排序的基础。期待你的深入思考和实现！

如何建立最大堆

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

我们可以从完全二叉树中的最后一个父节点开始，自底向上地使用维护堆特性的 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 仓库中查看源代码

在这篇文章中，我们学习了如何从一个随机数组构建最大堆。通过自底向上的方法和调用维护堆特性的 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] 看图聊算法：完全二叉树

喜欢本篇文章，记得动动小手点个