考研数据结构——C语言实现小顶堆

1. 数组初始化：

   • 首先，我们有一个整数数组arr，里面包含了一系列需要排序的数字。
   • 数组的长度n是通过对数组arr的总字节大小除以单个元素的字节大小得到的。

2. 小顶堆调整函数：

   • adjustHeapMin函数的作用是将数组中的元素从某个节点向下调整，以满足小顶堆的性质。在小顶堆中，父节点的值总是大于或等于子节点的值。
   • 函数从索引i的元素开始，将其与它的子节点（索引k）进行比较。
   • 如果子节点的值小于当前节点的值，并且子节点的值小于父节点的值，那么将子节点的值上移，即与父节点交换位置。
   • 这个过程一直进行，直到当前节点的值不再小于其子节点的值，或者已经到达数组的末尾（叶子节点）。

3. 交换函数：

   • swap函数是一个简单的辅助函数，用于交换数组中两个元素的位置。

4. 堆排序函数：

   • heapsortMin函数是堆排序的核心，它首先通过调用adjustHeapMin函数将整个数组构建成一个小顶堆。
   • 然后，它将堆顶元素（最小元素）与数组末尾的元素交换位置，这样数组的末尾就包含了一个有序的元素。
   • 交换后，数组的长度减少，因为最后一个元素已经是有序的了。
   • 接着，函数再次调用adjustHeapMin来重新调整堆的结构，确保除了最后一个元素之外的部分仍然是一个小顶堆。
   • 这个过程重复进行，直到整个数组都变为有序。

5. 主函数：

   • main函数是程序的入口点，它调用heapsortMin函数来对数组进行排序。
   • 排序完成后，通过一个循环遍历数组并打印出排序后的结果。

总结： 这段代码通过构建小顶堆，然后不断调整堆结构并交换堆顶元素与末尾元素，实现了数组的排序。这个过程是递归的，每次交换后都会减少堆的大小，并重新调整堆以保持小顶堆的性质。最终，数组中的元素将按照从小到大的顺序排列。

#include <stdio.h>
#include <stdlib.h>int arr[] = { 12,4,132,55,46,232,789,1,0,98,523,666 };
int n = sizeof(arr) / sizeof(arr[0]);// 调整为小顶堆
void adjustHeapMin(int i, int lef) {int temp = arr[i];int k;for (k = i * 2 + 1; k < lef; k = k * 2 + 1) {if (k + 1 < lef && arr[k] > arr[k + 1]) {k++;}if (arr[k] < temp) {arr[i] = arr[k];i = k;}else {break;}}arr[i] = temp;
}void swap(int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;
}// 小顶堆排序
void heapsortMin() {// 构建小顶堆for (int i = n / 2 - 1; i >= 0; i--) {adjustHeapMin(i, n);}// 调整堆结构+交换堆顶元素与末尾元素for (int j = n - 1; j > 0; j--) {swap(0, j);adjustHeapMin(0, j);}
}int main() {int i;heapsortMin();for (i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

运行结果如下：