【数据结构】_堆排序问题

1. 基于建堆的堆排序（需调HPPush）

2. 基于原数组的堆排序（仅调AdjustUp）

3. 堆排序建堆与升降序的总结

在专栏前文中，已经实现了堆的基本结构与相关方法；（小根堆）

详见下文：

【数据结构】_堆的实现-CSDN博客文章浏览阅读429次，点赞19次，收藏8次。专栏前文中，已经介绍了入堆及向上调整算法，出堆及向下调整算法，详情见下文：实际对于整除运算parent = (child - 1) / 2，parent并不会小于0，但当parent=0时，若a[parent] > a[child]，则再次进行child与parent的更新，使得parent与child均为0。当parent=0时，若若a[parent] > a[child]，则再次进行child与parent的更新，使得child更新为0，下次则无法进入while循环；https://blog.csdn.net/m0_63299495/article/details/145521676https://blog.csdn.net/m0_63299495/article/details/145521676修改向上调整与向下调整的比较逻辑，将堆修改为大根堆。

1. 基于建堆的堆排序（需调HPPush）

当前堆为大根堆，通过对数组元素逐个push进行建堆，再使用HPPop依次出堆顶元素，最终实现对原数组元素的降序排序：

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
void TestHeap1() {int a[] = { 4,2,8,1,5,6,9,7 };HP hp;HPInit(&hp);// 输出原始数组printf("orignal array: \n");for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++) {printf("%d ", a[i]);}printf("\n");// 建立小根堆，输出其顺序存储for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++) {HPPush(&hp, a[i]);}printf("minHeap array: \n");HPPrint(&hp);// 对原始数组使用堆排序，进行升序输出int i = 0;while (!HPEmpty(&hp)) {//printf("%d ", HPTop(&hp));a[i++] = HPTop(&hp);HPPop(&hp);}printf("Ascending sort: \n");for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++) {printf("%d ", a[i]);}printf("\n");HPDestory(&hp);
}
int main() {TestHeap1();return 0;
}

输出结果如下：

注：1、这种排序思路为实现排序需要额外开辟空间建堆，因为其调用了HPPush方法，空间复杂度为O(N)；

2、实现打印升序与降序只需修改向上调整和向下调整方法的对比大小关系，即可实现大根堆的降序和小根堆的升序排序：

2. 基于原数组的堆排序（仅调AdjustUp）

1、回顾已实现的Adjust方法:

void AdjustUp(HPDataType* a, int child);

其参数为数组与新插元素的下标，直接将数组视为一个完全二叉树，并不需要依赖于HPPush方法，故并不额外开辟空间，空间复杂度为O(1)；

现不调用HPPush方法，即对于已知数组不建堆，基于原数组仅调用向上调整算法进行堆排序。

2、以大根堆为例，调用AdjustUp方法后，在原数组上已经实现了大根堆的顺序存储（但并未申请额外空间），考虑其输出升降序问题：

（1）若想要实现降序排序：

调用AdjustUp方法后，当前数组已满足首元素为最大元素，则输出并删除堆顶的最大元素后，接下来需在剩下的元素中建新大根堆并再删除堆顶最大元素，这与初始考虑的直接删除堆顶元素的HPPop方法思路一致，会导致节点关系的错位与混乱，如此循环往复建堆与调整，虽可以实现最终的排序效果，但显然非常麻烦；

（2）若想要实现升序排序：

调用AdjustUp方法后，当前数组已满足首元素为最大元素，将堆顶元素与最末结点元素交换，再将其位置确定在数组尾，即现确定了最大的元素且保持原堆的大根堆基本关系与结构不变，再进行向下调整即可。如此循环，每次都确定未排序元素中最大的结点，并将其依次从后向前定位在数组中，从而实现了升序排序；

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
// 测试不建堆的排序
void HeapSort(int* a, int n) {// 建堆for (int i = 1; i < n; i++) {AdjustUp(a, i);}// 打印大根堆的顺序存储序列printf("maxHeap array: \n");for (size_t i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");// 交换首尾并删尾，再进行向下调整int end = n - 1;while (end>0) {Swap(&a[0], &a[end]);AdjustDown(a, end,0);end--;}// 打印升序排序结果printf("Ascending sort: \n");for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");
}
int main() {int a[] = { 4,2,8,1,5,6,9,7 };int sz = sizeof(a) / sizeof(a[0]);HeapSort(a,sz);return 0;
}

运行程序，结果为：