个人主页：仍有未知等待探索-CSDN博客
专题分栏：数据结构_仍有未知等待探索的博客-CSDN博客
欢迎大家来指教！
一、前言
今天要介绍的是堆排序。
首先什么是堆？简而言之，堆就是二叉树的数组形式，用数组来存储二叉树。
这个堆和C语言中讲的堆区是不同的两个概念，不要混淆。
二、堆排序
堆排序的核心就是构建一个特殊的二叉树，这个二叉树的特性是：其父节点大于等于（小于等于）其左右孩子结点。
故，最终创建的二叉树的根节点会是该二叉树的最大值（最小值）。
那怎么才能让整个数组中的数据有序呢？那我们就让数组中第一个数和最后一个数进行交换，然后以第一个数和倒数第二个数为端点，继续进行构建堆，然后选出次最小值。以此类推~~~
我以大根堆为例（从数组下标为1的地方开始存储）：
1、堆的数据类型
typedef int HpDataType;typedef struct Heap{HpDataType* a;//进行存储堆中的数据int size;//该堆的有效数据个数int capacity;//该堆中的容量}Hp;2、堆的初始化
//初始化void Heapinit(Hp* php){assert(php);//断言，如果php为空的话，报错php -> a = NULL;php -> size = 0;php -> capacity = 0;}3、堆的销毁
//堆的销毁void HeapDestory(Hp* php){assert(php);free(php -> a);//释放掉开辟的空间php -> a = NULL;//防止php -> a为野指针php -> size = 0;php -> capacity = 0;}4、堆的创建
// 堆的创建// k为要插入到堆里面的元素void Heap_push(Hp* php, int k){assert(php); //断言if (php -> size == php -> capacity)// 如果容量不够，扩容{// 如果容量为0，则给个初始值，否则就二倍扩容int size = php -> capacity == 0 ? 4 : php -> capacity * 2;Hp* tmp = (Hp* ) realloc(php -> a, (size + 1) * sizeof(int));if (tmp == NULL) {perror("realloc failed");exit(-1);// 扩容失败则结束程序}php -> a = tmp;php -> capacity = size;}// 插入到堆的最后php -> a[++ php -> size] = k;// 向上调整，如果比父节点要大就进行交换up(php -> a, php -> size);}5、向上调整
// 向上调整// idx为要调整元素的下标void up(int* a, int idx){assert(a);int child = idx;// 该结点下标int parent = child / 2;// 该结点的父节点，我是从下标为1开始存的while (child != 1){if (a[parent] < a[child]){Swap(&a[parent], &a[child]);}else{// 不需要调整，就退出break;}// 继续向上找child = child / 2;parent = parent / 2;}}6、删除堆的最后一个元素
该操作的主要作用是将该堆中最大的元素进行归位，并且进行调整除了最后一个元素的二叉树的顺序，使其仍为一个堆。
// 进行删除最后一个元素void Heappop(Hp* php){assert(php);assert(php -> size > 0);Swap(&php -> a[1], &php -> a[php -> size]);php -> size --;int parent = 1;int child = 2 * parent;while (child size){// 假设左节点最大，如果右结点比左节点大，就child存右节点下标if (child + 1 size && php -> a[child + 1] > php -> a[child]){child += 1;}// 判断孩子结点和父节点的值if (php -> a[parent] a[child]){Swap(&php -> a[parent], &php -> a[child]);}else {// 不需要则退出break;}parent = child;child = 2 * parent;}}7、取出堆顶元素
// 取出堆顶元素HpDataType Heaptop(Hp* php){assert(php);assert(php -> size > 0);return php -> a[1];}三、总代码及其运行结果
#define _CRT_SECURE_NO_WARNINGS1// 大根堆#include #include #include typedef int HpDataType;typedef struct Heap{HpDataType* a;// 进行存储堆中的数据int size;// 该堆的有效数据个数int capacity;// 该堆中的容量}Hp;void Heapinit(Hp* php);// 初始化void HeapDestory(Hp* php);// 堆的销毁void Heap_push(Hp* php, int k);// 堆的创建void Swap(int* a, int* b);// 交换void up(int* a, int idx);// 向上调整HpDataType Heaptop(Hp* php);// 取堆顶元素void Heappop(Hp* php);// 删除堆的最后一个元素int main(){int a[] = {1, 2, 3, 4, 5, 6, 7};Hp hp;Heapinit(&hp);int len = sizeof(a) / sizeof(a[0]);for (int i = 0; i < len; i++ ){Heap_push(&hp, a[i]);}printf("初始堆：\n");for (int i = 1; i 0){printf("%d ", Heaptop(&hp));Heappop(&hp);}HeapDestory(&hp);return 0;}// 初始化void Heapinit(Hp* php){assert(php);// 断言，如果php为空的话，报错php -> a = NULL;php -> size = 0;php -> capacity = 0;}// 堆的销毁void HeapDestory(Hp* php){assert(php);free(php -> a);// 释放掉开辟的空间php -> a = NULL;// 防止php -> a为野指针php -> size = 0;php -> capacity = 0;}void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}// 向上调整// idx为要调整元素的下标void up(int* a, int idx){assert(a);int child = idx;// 该结点下标int parent = child / 2;// 该结点的父节点，我是从下标为1开始存的while (child != 1){if (a[parent] size == php -> capacity)// 如果容量不够，扩容{// 如果容量为0，则给个初始值，否则就二倍扩容int size = php -> capacity == 0 ? 4 : php -> capacity * 2;Hp* tmp = (Hp* ) realloc(php -> a, (size + 1) * sizeof(int));if (tmp == NULL) {perror("realloc failed");exit(-1);// 扩容失败则结束程序}php -> a = tmp;php -> capacity = size;}// 插入到堆的最后php -> a[++ php -> size] = k;// 向上调整，如果比父节点要大就进行交换up(php -> a, php -> size);}// 取出堆顶元素HpDataType Heaptop(Hp* php){assert(php);assert(php -> size > 0);return php -> a[1];}// 进行删除最后一个元素void Heappop(Hp* php){assert(php);assert(php -> size > 0);Swap(&php -> a[1], &php -> a[php -> size]);php -> size --;int parent = 1;int child = 2 * parent;while (child size){// 假设左节点最大，如果右结点比左节点大，就child存右节点下标if (child + 1 size && php -> a[child + 1] > php -> a[child]){child += 1;}// 判断孩子结点和父节点的值if (php -> a[parent] a[child]){Swap(&php -> a[parent], &php -> a[child]);}else {// 不需要则退出break;}parent = child;child = 2 * parent;}}
谢谢大家！