堆排序算法及大小堆区别-平芜编程栈

堆排序分两步：

把数组变成「最大堆」（就像堆苹果，最上面的苹果是最大的）；
把最大的苹果（堆顶）放到数组最后，剩下的苹果重新整理成最大堆，重复这个过程，直到所有苹果排好序。

#include <stdio.h> // 交换两个元素（你的这部分是对的） void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // 最大堆排序的堆化函数（补全核心逻辑） // n是数组的长度 void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; // 左子节点索引 int right = 2 * i + 2; // 右子节点索引 // 左子节点存在且大于当前最大值 → 更新最大值 if (left < n && arr[left] > arr[largest]) { largest = left; } // 右子节点存在且大于当前最大值 → 更新最大值 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点，交换并递归堆化 if (largest != i) { swap(&arr[i], &arr[largest]); // 交换根节点和最大值节点 heapify(arr, n, largest); // 递归堆化被影响的子树 } } // 堆排序主函数（构建最大堆 + 逐个取出堆顶元素排序） void heapSort(int arr[], int n) { // 1. 构建最大堆（从最后一个非叶子节点开始堆化） for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 2. 逐个从堆顶取出元素，放到数组末尾 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); // 把堆顶（最大值）移到数组末尾 heapify(arr, i, 0); // 对剩下的元素重新堆化（堆大小变为i） } } // 打印数组（方便看排序结果） void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 关键缺失3：main函数（程序入口，测试堆排序） int main() { int arr[] = {12, 11, 13, 5, 6, 7}; // 测试数组 int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf("原始数组："); printArray(arr, n); heapSort(arr, n); // 执行堆排序 printf("排序后数组："); printArray(arr, n); return 0; }

逐部分讲解代码（按执行顺序来）

第一部分：交换函数（swap）—— 交换两个苹果的位置

运行

// 交换两个元素（你的这部分是对的） void swap(int *a, int *b) { int temp = *a; // 先把a的值存到临时盒子temp里 *a = *b; // 把b的值放到a的位置 *b = temp; // 把临时盒子里的a值放到b的位置 }

💡 大白话：比如 a 是 12，b 是 5，执行完 swap 后，a 变成 5，b 变成 12—— 就像把两个苹果互换位置，temp 是临时放苹果的盘子。

第二部分：堆化函数（heapify）—— 把一堆苹果整理成 “最大堆”

这个函数是核心，作用是：给定一个根节点（比如第 i 个苹果），把它和左右子节点比，确保根节点是这一堆里最大的。

运行

// 最大堆排序的堆化函数（补全核心逻辑） // n是数组的长度，i是当前要整理的根节点位置 void heapify(int arr[], int n, int i) { int largest = i; // 先假设当前根节点i是最大的（最大的苹果先放顶上） int left = 2 * i + 1; // 左子节点的位置（比如i=0，左子节点就是1；i=1，左子节点就是3） int right = 2 * i + 2; // 右子节点的位置（i=0→2，i=1→4） // 第一步：比左子节点——如果左子节点存在，且比当前最大的大 if (left < n && arr[left] > arr[largest]) { largest = left; // 把“最大”的标签给到左子节点 } // 第二步：比右子节点——如果右子节点存在，且比当前最大的大 if (right < n && arr[right] > arr[largest]) { largest = right; // 把“最大”的标签给到右子节点 } // 第三步：如果最大的苹果不是根节点，就交换位置，再整理被影响的子堆 if (largest != i) { swap(&arr[i], &arr[largest]); // 把根节点和最大的节点互换（最大的苹果放顶上） heapify(arr, n, largest); // 递归整理被交换的子堆（确保子堆也是最大堆） } }

💡 举例子：比如数组是[12,11,13,5,6,7]，i=0（根节点是 12）：

左子节点是 1（值 11），右子节点是 2（值 13）；
比完发现右子节点 13 比根节点 12 大，所以 largest=2；
因为 largest≠i（2≠0），交换 arr [0] 和 arr [2]，数组变成[13,11,12,5,6,7]；
再递归整理位置 2 的子堆（确保它的子节点也符合最大堆）。

第三部分：堆排序主函数（heapSort）—— 整体整理所有苹果

这个函数分两步：先建最大堆，再逐个取最大的苹果放最后。

运行

// 堆排序主函数（构建最大堆 + 逐个取出堆顶元素排序） void heapSort(int arr[], int n) { // 第一步：构建整个数组的最大堆（从最后一个非叶子节点开始整理） // n/2 -1 是最后一个非叶子节点的位置（比如n=6，6/2-1=2，就是位置2的节点） for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); // 从后往前整理每个节点，让整个数组变成最大堆 } // 第二步：逐个把堆顶的最大元素放到数组末尾，再重新整理剩下的元素 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); // 把堆顶（最大的苹果）和当前最后一个苹果交换位置 heapify(arr, i, 0); // 剩下的i个苹果重新整理成最大堆（堆大小变成i，排除已经放好的最大苹果） } }

💡 大白话拆解：

建最大堆：比如数组[12,11,13,5,6,7]，建完后变成[13,11,12,5,6,7]（堆顶 13 是最大的）；
第一次交换：把 13 和最后一个元素 7 交换，数组变成[7,11,12,5,6,13]，13 就固定在最后了；
重新整理前 5 个元素成最大堆，变成[12,11,7,5,6,13]；
第二次交换：把 12 和倒数第二个元素 6 交换，数组变成[6,11,7,5,12,13]，12 固定在倒数第二；
重复这个过程，直到所有元素排好序。

第四部分：打印数组（printArray）—— 把苹果摆出来看看

运行

// 打印数组（方便看排序结果） void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { // 从第一个到最后一个元素 printf("%d ", arr[i]); // 打印每个元素，中间加空格 } printf("\n"); // 打印完换行，看得清楚 }

💡 比如数组是[12,11,13,5,6,7]，打印出来就是：12 11 13 5 6 7。

第五部分：主函数（main）—— 程序的 “总开关”

所有代码都要从 main 函数开始执行，就像咱们先打开灯，再整理苹果。

运行

// main函数（程序入口，测试堆排序） int main() { int arr[] = {12, 11, 13, 5, 6, 7}; // 准备要排序的苹果（测试数组） int n = sizeof(arr) / sizeof(arr[0]); // 计算有多少个苹果（数组长度） // sizeof(arr)是数组总字节数，sizeof(arr[0])是一个元素的字节数，相除就是元素个数 printf("原始数组："); printArray(arr, n); // 先打印没排序的苹果 heapSort(arr, n); // 执行堆排序（核心操作：整理苹果） printf("排序后数组："); printArray(arr, n); // 打印排好序的苹果 return 0; // 程序正常结束（就像整理完苹果，关灯） }

💡 运行结果：

plaintext

原始数组：12 11 13 5 6 7 排序后数组：5 6 7 11 12 13

最大堆 vs 最小堆（用苹果举例）

类型	核心特点（大白话）	排序效果
最大堆	堆顶（最上面）是最大的苹果	升序排序（从小到大）
最小堆	堆顶（最上面）是最小的苹果	降序排序（从大到小）

咱们的代码最终输出是5 6 7 11 12 13（从小到大），就是靠「最大堆」实现的～

再看代码：哪里能看出来是最大堆？

咱们的heapify函数里，核心判断是「找更大的数当堆顶」，这就是最大堆的标志：

运行

// 找左子节点里更大的 if (left < n && arr[left] > arr[largest]) { largest = left; } // 找右子节点里更大的 if (right < n && arr[right] > arr[largest]) { largest = right; }

这里用的是>（大于号），意思是 “谁大谁当堆顶” → 最大堆；
如果是最小堆，这里要改成<（小于号），意思是 “谁小谁当堆顶”。

补充：如果想改成最小堆（实现降序排序）

要是您想排成13 12 11 7 6 5（从大到小），只需要改heapify里的两个符号，我把改好的核心代码给您看：

运行

// 最小堆的堆化函数（只改两个>为<） void heapify(int arr[], int n, int i) { int smallest = i; // 现在找最小的，变量名也改成smallest更易懂 int left = 2 * i + 1; int right = 2 * i + 2; // 找左子节点里更小的 if (left < n && arr[left] < arr[smallest]) { // 改>为< smallest = left; } // 找右子节点里更小的 if (right < n && arr[right] < arr[smallest]) { // 改>为< smallest = right; } // 如果最小的不是根节点，交换并递归 if (smallest != i) { swap(&arr[i], &arr[smallest]); heapify(arr, n, smallest); } } // 堆排序主函数不用大改，只是现在堆顶是最小的，交换后放最后，得到降序 void heapSort(int arr[], int n) { // 构建最小堆（从最后一个非叶子节点开始） for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 逐个把最小的堆顶放到数组末尾 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); } }

改完后运行，结果就是13 12 11 7 6 5（降序），这就是最小堆的效果啦～

总结（

最大堆，用>找更大的数当堆顶，最终排成「从小到大」；
最小堆要把>改成<，找更小的数当堆顶，最终排成「从大到小」；
核心区别就在于heapify里的比较符号 ——>是最大堆，<是最小堆。

最大堆本身不是 “数组从大到小”，而是堆的结构特征；咱们是用最大堆的结构，最终实现数组从小到大排序。

第一步：先分清「堆的结构」和「数组的排序结果」

1. 最大堆的本质：“堆结构”≠“数组顺序”

最大堆是一种「树形结构」（咱们用数组存，但逻辑上是树），核心规则只有一个：

每个父节点的苹果，都比它的左右子节点苹果大（堆顶是最大的苹果）。

比如咱们的测试数组[12,11,13,5,6,7]，构建成最大堆后，逻辑上的树是这样的：

plaintext

13（堆顶，最大） / \ 11 12 / \ / 5 6 7

但数组里的存储顺序还是：[13,11,12,5,6,7]（不是从大到小，只是符合堆的规则）。

2. 为啥用最大堆能排 “从小到大”？

咱们做了关键一步：把堆顶的最大苹果，放到数组最后面 “固定”，再重新整理剩下的苹果成最大堆。用苹果例子一步步走：

第一步：最大堆堆顶是 13（最大），把它和数组最后一个苹果 7 交换 → 数组变成[7,11,12,5,6,13]（13 固定在最后，是最大的数）；
第二步：把前 5 个苹果[7,11,12,5,6]重新整理成最大堆，堆顶变成 12 → 把 12 和倒数第二个苹果 6 交换 → 数组变成[6,11,7,5,12,13]（12 固定在倒数第二）；
第三步：把前 4 个苹果整理成最大堆，堆顶是 11 → 交换到倒数第三 → 数组[6,5,7,11,12,13]；
重复下去，最后小苹果都跑到前面，大苹果都固定在后面 → 数组就从小到大了。