<你想看的我这里都有😎 >
数组建堆
我们能不能不消耗空间就完成一次建堆？直接将所给的数组建堆可以吗？
这些数字在物理逻辑上是一个数组，而在虚拟逻辑上是一个完全二叉树，那么将这个完全二叉树进行一些调整后是不是就能得到一个堆呢？我们尝试利用之前的向上调整算法，完成建堆的操作：
上述操作的本质就是模拟堆插入的过程建堆
（第一个视为堆，第二个插入然后向上调堆、第一个和第二个视为堆，第三个插入然后向上调堆）
可以发现我们在没有申请内存空间的前提下，仅利用一个向上调整算法就完成了将数组建小堆的操作，但是如果我们在选出这个小堆中的最小值后，再想要选出这个堆中的次小值就会出现问题：
可以发现当要选出次小值时，缺少了”1“的小堆的剩余元素并不能算作是一个小堆，所以为了选出次小值，我们还要建堆，以此类推这就相当于选一次值就要建一次堆，那还不如直接选用时间复杂度为O（n）的暴力遍历数组选取最小或次小值，而我们建堆的目的就是为了方便我们选出我们想要的最大/小、次大/小的值，但是很明显如果仅利用向上调整算法建立一个小堆是无法满足我们的需求的，所以我们应该利用向上调整算法去建立一个大堆
关于为什么要重新建堆而不是调整的解释：
当我们取出最大值1后，小堆的性质被破坏了。由于元素1被移除，并且无法通过向下调整操作来恢复小堆性质（即使你将大于号与小于号互换），所以我们需要重新建立一个有效的小堆，这就显得很麻烦了。
结论：仅用向上调整算法建小堆，若取出最小值，那么剩下的数有可能不是堆，故应建大堆
只需要该算法做一些调整，将(a[child] < a[parent])变为(a[child] > a[parent])，就可以建大堆：
调整后的结果是我们得到了一个大堆，此时即使将堆顶的“9”删除，剩余的两个子树也仍然保留大堆的性质，这就意味着我们在选出最小数及次小数后只需要进行向下调整即可不需要考虑重新建堆，当我们想要最大值，只需要交换首尾元素的位置，然后将尾部元素不再视为堆的一部分即可，此时就相当于获取了堆中的最大值，想要获取次大值重复以上操作即可：
取出（不再视为堆的一部分）即选出该数
堆排序
其实上述的内容，就是我们实际中堆排序的一种实现方式，即利用向上调整算法建大堆然后再利用向下调整算法将挑选后剩余的元素重新调整为虚拟逻辑上的大堆以便下一次的选取。
堆排序本质上是一种选择排序（Selection Sort）
利用向上/下调整算法将数组中的数字在虚拟逻辑上重新变为大/小堆与重新建堆的区别是？
在堆排序算法中，我们需要构建一个最大/小堆来进行排序。这可以通过两种方式实现：
1. 重新建堆：这是一种直接的方法，从数组的首元素开始逐个插入到空堆中，步骤如下：
- 创建一个空的堆
- 将数组中的元素逐个插入到空堆中
- 最终得到了一个满足最大（或最小）堆性质的完整二叉树
2. 向上/下调整：这是一种当已有部分构成的近似完全二叉树进行调整来达到目标状态的方法
- 向上调整：从某节点开始，将其与父节点比较并交换位置，直至满足最大/小堆性质。该过程会将当前节点及其祖先节点推向正确位置，并保持子树仍然满足对应性质
- 向下调整：从某节点开始，将其与左右子节点比较并交换位置，直至满足最大/小堆性质。该过程会使当前节点及其后代子树变为有序树，并保持其他部分仍然满足对应性质
3、区别：
- 重新建堆是一种从零开始构建堆的方法，它将整个数组视为初始状态，并按顺序插入元素来构建最大（或最小）堆。这种方法需要较多的时间和空间复杂度。
- 向上调整和向下调整算法是在已有部分近似完全二叉树的基础上进行调整，通过比较节点与其父节点或子节点来达到维护最大（或最小）堆性质的目标。这两种算法可以在不重建完全二叉树的情况下对特定位置进行优化操作，因此具有更高效率。
4、总结：
- 如果已拥有一个无序数组并希望将其转换为一个满足最大/小堆性质的完全二叉树，则可以使用重新建堆方法
- 如果你已经拥有一个近似完全二叉树，并且只需对其中某些位置进行修正以满足最大（或最小）堆性质，则应使用向上调整或向下调整算法
利用向上调整算法实现堆排序（升序）
使用向上调整算法实现堆排序的步骤如下：
- 构建大堆：从数组的第一个非叶子节点开始，依次对每个节点进行向上调整操作，使其满足最大堆性质。
- 维护：交换首尾元素，并将末尾元素从堆中移除。然后对新的根节点进行一次向下调整操作，以维持最大堆性质，重复这个过程直到所有元素都被移除并排好序。
具体代码如下：
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; //指向存储元素的指针 int capacity; //当前顺序表容量 int size; //当前顺序表的长度 }HP; //交换父子位置 void Swap(HPDataType* p1,HPDataType* p2) { HPDataType* tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整，此时传递过来的是最后一个孩子的元素下标我们用child表示 void AdjustUP(HPDataType* a,int child) { //由于我们要调整父亲与孩子的位置所以此时也需要父亲元素的下标，而0父亲元素的下标值 = （任意一个孩子的下标值-1）/ 2 int parent = (child - 1) / 2; //当孩子等于0的时位于树顶（数组首元素的位置），树顶元素没有父亲，循环结束 while(child > 0) { //如果孩子还未到顶且它的下标对应的元素值小于它的父亲的下标对应的元素值，就将父子位置交换，交换玩后还要将下标对应的值“向上移动” if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } //由于这是一个小堆，所以当孩子大于等于父亲时不需要交换，直接退出循环即可 else { break; } } } //向下调整算法 void AdjustDown(HPDataType* a, int size, int parent) { //根据之前的推论，左孩子的下标值为父亲下标值的两倍+1，左孩子的下标值为父亲下标值的两倍+2 int child = parent * 2 + 1; //循环结束的条件是走到叶子结点 while (child < size) { //假设左孩子小，若假设失败则更新child，转换为右孩子小，同时保证child的下标不会越界 if (child + 1< size && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent]) { //如果此时满足孩子小于父亲则交换父子位置，同时令父亲的下标变为此时的儿子所在下标，儿子所在下标变为自己的儿子所在的下标（向下递归） Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } //如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆，不再需要向下调整算法，循环结束 else { break; } } } //降序堆排序 void HeapSort(int* a, int n) { //构建大堆 for (int i = 1; i < n; i++) { AdjustUP(a, i); } //维护 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] = { 4,6,2,1,5,8,2,9 }; HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } //HeapSort(a, i); return 0; }
仅利用向上调整算法建大堆的结果：
建大堆后利用向下调整算法升序堆排序的结果：
画图演示如下：
向上调整算法建大堆
向下调整算法升序堆排序：
由于是手绘的，字迹不好看请见谅
但其实相比于写一个向上调整算法去建堆，然后再写一个向下调整算法去维护堆，最后完成升序堆排序，我们其实可以仅利用向下调整算法实现这些内容，并不需要额外的编写向上调整算法，同时向下调整算法的时间复杂度为O（N）而向上调整算法的时间复杂度为O（N*logN），向下调整算法的时间复杂度要小于向上调整算法的时间复杂度......
利用向下调整算法实现堆排序（降序）
使用向下调整算法实现降序堆排序的步骤如下：
- 构建小堆：从数组的最后一个非叶子节点开始，向上遍历到根节点，对于当前节点，比较它与其左右子节点的值，并找到其中最小的值和对应索引，如果当前节点的值大于子节点，则将两者交换位置，将当前节点更新为被交换过后的子节点，并重复步骤2和3，直到达到叶子结点或不需要再进行交换。
- 维护：将根节点（数组首元素）与末尾元素交换位置，并将末尾元素从堆中移除。然后对新的根节点进行一次向下调整操作，以维持最小堆性质。重复这个过程直到所有元素都被移除并排好序。
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; //指向存储元素的指针 int capacity; //当前顺序表容量 int size; //当前顺序表的长度 }HP; //交换父子位置 void Swap(HPDataType* p1,HPDataType* p2) { HPDataType* tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整算法 void AdjustDown(HPDataType* a, int size, int parent) { //根据之前的推论，左孩子的下标值为父亲下标值的两倍+1，左孩子的下标值为父亲下标值的两倍+2 int child = parent * 2 + 1; //循环结束的条件是走到叶子结点 while (child < size) { //简单来说就是看俩子结点谁更小 //假设左孩子小，若假设失败则更新child，转换为右孩子小，同时保证child的下标不会越界 if (child + 1< size && a[child + 1] < a[child]) { ++child; } if (a[child] < a[parent]) { //如果此时满足孩子小于父亲则交换父子位置，同时令父亲的下标变为此时的儿子所在下标，儿子所在下标变为自己的儿子所在的下标（向下递归） Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } //如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆，不再需要向下调整算法，循环结束 else { break; } } } //堆排序 void HeapSort(int* a, int n) { //构建小堆 for(int i = (n-1-1)/2;i>=0;--i) { AdjustDown(a,n,i); } //维护 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] = { 4,6,2,1,5,8,2,9 }; HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } //HeapSort(a, i); return 0; }
仅利用向下调整算法建小堆的结果：
建小堆后利用向下调整算法降序堆排序的结果：
画图演示如下：
至于为什么在一颗子树上调整的时候就不需要考虑另一颗子树，这是因为我们选出根节点的两个子结点中的最小值了，那么另一个根结点就不可能是整个堆的次小值，所以我们转换为从另一子结点开始......
利用向下调整算法实现堆排序（升序）
使用向下调整算法实现升序堆排序的步骤如下：
- 构建大堆：从数组的最后一个非叶子节点开始，向上遍历到根节点，对于当前节点，比较它与其左右子节点的值，并找到其中最大的值和对应索引，如果当前节点的值小于子节点，则将两者交换位置，将当前节点更新为被交换过后的子节点，并重复步骤2和3，直到达到叶子结点或不需要再进行交换。
- 维护：将根节点（数组首元素）与末尾元素交换位置，并将末尾元素从堆中移除。然后对新的根节点进行一次向下调整操作，以维持最大堆性质。重复这个过程直到所有元素都被移除并排好序。
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; //指向存储元素的指针 int capacity; //当前顺序表容量 int size; //当前顺序表的长度 }HP; //交换父子位置 void Swap(HPDataType* p1,HPDataType* p2) { HPDataType* tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整算法 void AdjustDown(HPDataType* a, int size, int parent) { //根据之前的推论，左孩子的下标值为父亲下标值的两倍+1，左孩子的下标值为父亲下标值的两倍+2 int child = parent * 2 + 1; //循环结束的条件是走到叶子结点 while (child < size) { //简单来说就是看俩子结点谁更小 //假设左孩子小，若假设失败则更新child，转换为右孩子小，同时保证child的下标不会越界 if (child + 1< size && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent]) { //如果此时满足孩子小于父亲则交换父子位置，同时令父亲的下标变为此时的儿子所在下标，儿子所在下标变为自己的儿子所在的下标（向下递归） Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } //如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆，不再需要向下调整算法，循环结束 else { break; } } } //堆排序 void HeapSort(int* a, int n) { //构建小堆 for(int i = (n-1-1)/2;i>=0;--i) { AdjustDown(a,n,i); } //维护 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } int main() { int a[] = { 4,6,2,1,5,8,2,9 }; HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } //HeapSort(a, i); return 0; }
仅利用向下调整算法建大堆的结果：
建大堆后利用向下调整算法升序堆排序的结果：
不再画图展示......
代码中的注释内容可看可不看 ，懒得改了
结论：在进行升序和降序堆排序时更多的仅使用向下调整算法就可以完成
关于上述内容涉及的相关时间复杂度的计算，我们放在了：堆的相关时间复杂度计算（C语言）
~over~
