个人主页:仍有未知等待探索-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;}}

谢谢大家!