锐客网

  1. 首页 > 生活百科 > it技术 > >

笔记|堆的实现+堆排序

链表数据结构c语言笔记开发语言

咱们开门见山，直奔主题！！
目录
一，堆的定义
1.概念
2.性质
3.结构
二、堆的实现
定义
初始化和销毁
数据入队
堆的插入图解
交换函数
向上调整函数
出堆
图解
向下调整函数
向下调整函数优化
堆空判断，堆长，堆顶元素
堆元素打印
三，堆排序

一，堆的定义 1.概念 堆就是一棵可以自我平衡的完全二叉树，存储结构连续，可看作是顺序表。
笔记|堆的实现+堆排序
文章图片


2.性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
3.结构 堆的逻辑结构为一颗完全二叉树，但实际上在内存中的存储是连续的，那么要实现它就可以想到用顺序表来实现。
笔记|堆的实现+堆排序
文章图片


二、堆的实现 定义 数据类型记得重定义
依据上述内容，我们用顺序表来实现堆
size记录有效元素个数，capacity记录空间大小
typedef int HPDataType; typedef struct Heap { HPDataType* a; size_t size; size_t capacity; }HP;

初始化和销毁 指向顺序表开头的的地址a置空
空间大小和有效元素个数都为0
void HeapInit(HP* php) { assert(php); php->a = NULL; php->capacity = php->size = 0; }

因为空间是连续开辟的，只需要释放起始地址，后面的空间会随之释放
之后将空间和元素个数置0即可
void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; }

数据入队
数据入堆=插入顺序表
先判断空间大小是否足够，初始空间给4个，之后每次扩容原容量的二倍
用realloc进行扩容，记得进行判断，这里我暴力些，直接断言
记得更新空间大小
注：堆有大堆和小堆，插入数据后，必须保证堆的结构还是大堆或小堆
无论是大堆或小堆，最大数据或最小数据都在堆顶，若插入数据不符合堆的结构，那么必须将数据向上调整。是孩子结点和双亲结点间的调整
堆的插入图解
笔记|堆的实现+堆排序
文章图片

交换函数
从图看出必须进行两个数的交换，那么我们单独写出一个交换函数
void swap(HPDataType* pa, HPDataType* pb) { HPDataType* tmp = *pa; *pa = *pb; *pb = tmp; }

下面是插入数据的代码，为了简便一点，我们把向上调整单独拿出来
向上调整函数
注意：存储结构是顺序表，下标从0开始，若顺序表size=1，有效数据为1，那么数据在下标为0的位置上，所以child=php->size-1，这里面child和parent为元素下标。
//向上调整 void Up(HPDataType* a,size_t child) { size_t parent = (child - 1) / 2; while (child>0) { if (a[child] < a[parent]) { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }

void HeapPush(HP* php, HPDataType x) { assert(php); //插入元素 if (php->size==php->capacity) { size_t newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*newcapacity); assert(tmp); php->a = tmp; php->capacity = newcapacity; } php->a[php->size] = x; php->size++; //保证是堆的结构 //向上调整 size_t child = php->size - 1; //size_t parent = (child-1) / 2; //while (child>0) //{ // if (php->a[child] < php->a[parent]) // { ////HPDataType data = https://www.it610.com/article/php->a[parent]; ////php->a[parent] = php->a[child]; ////php->a[child] = data; //swap(&php->a[child], &php->a[parent]); //child = parent; //parent = (child - 1) / 2; // } // else // { //break; // } //} Up(php->a,child); }

出堆 删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
图解
笔记|堆的实现+堆排序
文章图片

交换后保持堆的结构，必须将数据即堆顶元素与他的最小或最大孩子进行交换（要看是大堆还是小堆，小堆和小孩子交换，大堆和大孩子交换）
向下调整函数
向下调整必然要循环执行，必须要左孩子和右孩子都小于有效个数size，左孩子一定小于右孩子，判断条件只需要右孩子小于size即可。
代码以小堆为例：
我分了两条逻辑线（有些繁琐，下面有优化）：
左孩子小的情况和右孩子小的情况
交换数据，双亲结点和两个孩子结点下标进行更新
当数据相等时退出循环
void Down(HPDataType* a,size_t parent,size_t size) { size_t lchild = parent*2 + 1; size_t rchild = parent*2 + 2; while (rchilda[rchild]) { if (a[parent] > a[rchild]) { swap(&a[parent], &a[rchild]); parent = rchild; lchild = parent*2 + 1; rchild = parent*2+ 2; } } else { break; } } }

向下调整函数优化
对上面代码的优化，直接确定一个孩子child，默认它是左孩子，第一个if处必须判断child+1小于size，防止越界。
如果右孩子小于左孩子，左孩子++直接等于右孩子，否则不变
之后直接判断双亲结点和孩子的大小完成互换或者退出
//down优化 void Down(HPDataType* a, size_t parent, size_t size) { size_t child = parent * 2 + 1; while (child < size) { if (child + 1

//删除堆顶数据 //互换堆顶和末尾数据，向下调整 void HeapPop(HP* php) { assert(php); assert(php->size > 0); size_t parent = 0; swap(&php->a[0],&php->a[php->size-1]); php->size--; Down(php->a,parent,php->size); }

堆空判断，堆长，堆顶元素
bool HeapEmpty(HP* php) { assert(php); return php->size == 0; } size_t HeapSize(HP* php) { assert(php); return php->size; } HPDataType HeapTop(HP* php) { assert(php); assert(php->size>0); return php->a[0]; }

堆元素打印
void HeapPrint(HP* php) { assert(php); for (size_t i=0; isize; i++) { printf("%d ",php->a[i]); } printf("\n"); }

三，堆排序
给一组数据让他变成有序
建立一个堆，将数据进行入堆，判断堆是否为空
之后将堆顶元素更新至数组里，注意要出堆堆顶元素，堆顶元素永远都是最大或最小
打印更新后的数据，就完成了一组数据的排序
//堆排序 void HeapSort(int* a,int size) { HP hp; HeapInit(&hp); for (int i = 0; i

笔记|堆的实现+堆排序
文章图片

快来点赞评论吧，铁铁们~~~~~~~~~~~~
笔记|堆的实现+堆排序
文章图片

【笔记|堆的实现+堆排序】

    推荐阅读


    上一篇：笔记|动态内存管理分析理解

    下一篇：有趣例题|力扣 142.环形链表