定义
堆是一个满足堆序性的完全二叉树。完全二叉树有以下性质：
- 完全二叉树只允许最后一行不为满
- 最后一行必须从左往右排序
- 最后一行元素之间不可以有间隔
示例：
反例：
堆序性
大根堆：每个父结点元素大于子结点元素
小根堆：每个父结点元素小于子结点元素
示例：
堆的存储
堆的底层实现是一个数组，节点按层序遍历的顺序存入。数组下标直接对应了节点在堆中的位置，从而可以快速计算父子节点的关系。
堆的父子结点满足如下规律：
结点下标为i的左子结点下标为2i + 1，右子结点的下标为2i + 2。
堆的基本操作
下滤
堆的下滤是指当堆顶元素被删除或替换后，为了维持堆的性质，将该元素从上向下与较大的子节点比较并交换，直到找到其正确位置的操作。
观察如下一棵二叉树，可以看到只有根结点不满足堆序性，如何操作才能把这棵树调整成堆呢？下面以大根堆为例，逐步完成由树向堆的调整。
- 从需要调整的节点（通常是根节点）开始。
- 将该节点与其左右子节点中较大的一个进行比较。
- 如果该节点小于这个较大的子节点，则交换它们的位置。
- 重复步骤2和3，直到该节点大于或等于其所有子节点，或者到达堆的底部（成为叶节点）。
过程示意如下：
 |
 |
 |
|---|
上滤
类比下滤，上滤是当最后一个结点破坏了堆序性时将其调整成堆所进行的操作。形象一点说就是让一个新插入末尾的节点从下往上冒到合适的地方。
 |
 |
|---|
建堆
有两种建堆的方法，分别对应上文中的两种操作。
自顶向下 ：将数组中的元素从根结点开始逐个插入堆中，每次插入都要进行上滤操作（如果破坏堆序性）。时间复杂度为O(n log n)。
自底向上：将数组中的元素从根结点开始逐个插入堆中，然后先把下面的元素调整成堆，再对父元素进行下滤操作。具体操作是从倒数第二排开始（最后一个非叶子节点），对每个父结点进行下滤操作，直到根结点操作完毕。自底向上的时间复杂度为O(n)。
优先队列
优先队列是一种非常实用且高效的数据结构，它确保每次被访问或移除的元素都是当前集合中优先级最高（或最低）的那一个，堆是实现优先队列的理想数据结构。
步骤详解
优先队列的核心操作主要包括插入和删除最高优先级元素，这些操作依赖于堆的上滤和下滤过程来维持其结构。
插入新元素
当向优先队列中插入一个新元素时，需要将其放置到正确的位置以维持堆序性。这个过程称为上滤：
- 置于末尾：首先，将新元素添加到堆的末尾，也就是完全二叉树的最后一个位置。
- 向上比较：然后，将这个新元素与其父节点进行比较。
- 交换位置：如果新元素的优先级高于其父节点（在大根堆中意味着值更大），就将它与父节点交换位置。
- 重复上滤：交换后，在新位置上继续与新的父节点比较，重复步骤2和3，直到新元素的优先级不高于其父节点，或者它到达了堆顶（根节点）。
经过上滤操作，新元素被“滤”到了合适的位置，堆序性得以恢复。
删除最高优先级元素
当需要取出当前优先级最高的元素时，操作如下。这个过程的核心是下滤：
- 取出堆顶：直接移出堆顶元素（对于大根堆，这就是最大元素），这个元素就是我们需要的结果。
- 填补空缺：将堆的最后一个元素移动到原本的堆顶位置，以填补空缺。
- 向下比较：将这个新移到堆顶的元素与其子节点进行比较。
- 交换位置：如果它的优先级低于其子节点中优先级更高的那一个（在大根堆中意味着值更小），就将它与该子节点交换位置。
- 重复下滤：交换后，在新位置上继续与新的子节点比较，重复步骤3和4，直到该元素的优先级不低于其任何子节点，或者它已经成为了叶节点。
经过下滤操作，新的堆顶元素被“滤”到了合适的位置，堆序性再次恢复。
堆排序
根据上文描述不难推出只要将优先队列的所有元素依次弹出不就实现了排序吗？
 |
 |
|---|
但是实际上考虑到空间复杂度，并不会开辟新的空间来存储弹出的元素，而是会利用原本的堆结构，将排序的结果存放到堆空缺的单元内。以下是实际的堆排序的过程。
堆排序的核心思想非常直观：利用堆这种数据结构的特性，不断从堆顶取出当前最大（或最小）的元素，然后重新调整堆，直到所有元素有序。
具体来说，如果你想要升序排列数组，通常会构建一个最大堆（大根堆：每个节点的值都大于或等于其子节点的值）。这样，堆顶元素就是当前最大的数。然后：
- 将堆顶元素（最大值）与堆的最后一个元素交换。（其实可看作两步：先将堆顶元素弹出，然后将最后一个元素放入堆顶，再将弹出的堆顶元素放入空缺的最后一个元素位置中）
- 排除这个已经找到的最大值（可以看作有序部分从末尾开始建立），对剩余的元素重新调整成最大堆。
- 重复上述步骤，直到堆中只剩下一个元素。
关键步骤与算法实现
实现堆排序的关键在于两个核心操作：构建初始堆和维护堆性质的向下调整（heapify）。
构建初始堆
我们无需从零开始一个个插入元素来建堆。一个更高效的方法是，直接将待排序的数组视为一个完全二叉树，然后从最后一个非叶子节点开始，向前依次对每个节点执行向下调整操作（即上文所述的自底向上的建堆方法）。
为什么是最后一个非叶子节点？因为在一个完全二叉树中，叶子节点本身可以看作是只有一个元素的堆，已经满足堆的性质，无需调整。最后一个非叶子节点的索引可以通过公式 n/2 - 1计算（假设数组下标从0开始）。
向下调整算法
这是堆排序的灵魂。它的作用是：当某个节点的值小于其子节点时，通过让它“下沉”，来恢复堆的性质。
- 对于给定节点，找出其左子节点（
2*i+1）和右子节点（2*i+2）。 - 在父节点和两个子节点中，找出值最大的那个。
- 如果最大值不是父节点，就交换父节点和这个最大子节点。
- 交换后，被交换下去的节点可能会破坏它新位置子树的堆性质，因此需要递归地或迭代地对这个子树继续执行向下调整，直到无法交换或到达叶子节点。
性能分析与特点
堆排序是一种非常高效的排序算法，其性能特征非常稳定。
时间复杂度：无论在最好、最坏还是平均情况下，堆排序的时间复杂度都是 O(n log n)。这是因为建堆过程的时间复杂度是O(n)，而每次调整堆的时间复杂度是O(log n)，总共需要进行n次调整。
简单来说，堆排序的时间复杂度计算如下：
总时间 = 建堆时间 + 排序时间 = O(n) + O(n log n) = O(n log n)虽然建堆过程本身是 O(n)，但后续占主导地位的排序循环是 O(n log n)。根据渐进分析原则，我们取最高阶项，所以堆排序的整体时间复杂度就是 O(n log n)。
空间复杂度：堆排序是原地排序算法，只需要常数级别（O(1)）的额外空间用于元素交换，非常节省内存。
稳定性：堆排序是不稳定的排序算法。在交换堆顶和末尾元素时，可能会改变相同值元素的原始相对顺序。如果只是单纯地对一组数字（比如考试成绩）进行排序，那么两个同为90分的同学谁先谁后通常没关系。当需要多次排序或排序对象是复合数据时，稳定性就至关重要了。
评论区