河北智能网站建设,潍坊专业汽车贴膜,济宁一建建设集团有限公司,广东省室内设计公司排名文中代码源文件已上传#xff1a;数据结构源码 -上一篇 初级数据结构#xff08;五#xff09;——树和二叉树的概念 | NULL 下一篇-
1、堆的特性
1.1、定义 堆结构属于完全二叉树的范畴#xff0c;除了满足完全二叉树的限制之外#xff0c;还满… 文中代码源文件已上传数据结构源码 -上一篇 初级数据结构五——树和二叉树的概念 | NULL 下一篇-
1、堆的特性
1.1、定义 堆结构属于完全二叉树的范畴除了满足完全二叉树的限制之外还满足所有父节点数据的值均大于或小于子节点。 父节点大于子节点的堆称为大堆或大根堆反之则称为小堆或小根堆。 下面例子由于红色节点不符合堆的定义所以不是堆。 1.2、实现方式 由于堆每插入一个数据它的位置是确定的所以一般都是以顺序表构建堆插入新节点只相当于顺序表的尾插。这个顺序表与本系列第一篇里定义的顺序表可以说完全一样区别只在于对表的操作上。当然你也可以用二叉节点或者三叉节点来创建堆但这样一来后续对堆的操作会特别繁琐。 在这里需要重点理解以顺序表来创建堆其实际结构是线性的但我们通过对下标序号附以一定意义把它抽象成树结构。 访问顺序我们可以先回顾上一篇里的两张图 顺序表第一个元素下标为 0 我们以它作为根节点子节点在顺序表中的下标分别是父节点下标的二倍 1 和二倍 2 。
size_t child_1 parent * 2 1;
size_t child_2 parent * 2 2;
size_t parent (child_1 - 1) / 2;
size_t parent (child_2 - 1) / 2; 若取下标为 1 的位置作为根节点的情况下 0 的位置空置即可子节点在顺序表中的下标分别是父节点下标的二倍和二倍 1 。
size_t child_1 parent * 2;
size_t child_2 parent * 2 1;
size_t parent child_1 / 2;
size_t parent child_2 / 2;
2、堆构建
2.1、文件结构 以顺序表的方式构建堆这次选用柔性数组的结构体形式。与之前相同的三个文件 heap.h 用于创建项目的结构体类型以及声明函数 heap.c 用于创建堆各种操作功能的函数 main.c 仅创建 main 函数用作测试。
2.2、前期工作 heap.h 中内容如下。这里需要注意的是由于堆是以 malloc 形式创建的空间以指针记录销毁堆的函数最终需要把该指针变量置空所以需要传指针的地址。而插入数据和删除数据由于涉及 realloc 有异地扩容的可能同样需要改变堆指针记录的地址所以这三个函数参数都必须定义为二级指针
#include stdio.h
#include stdlib.h//大堆大于号 小堆小于号
#define COMPARE //存储数据类型的定义及打印占位符预定义
#define DATAPRT %d
typedef int DATATYPE;//堆结构体类型
typedef struct Heap
{size_t size; //记录堆内数据个数size_t capacity; //记录已开辟空间大小DATATYPE data[0]; //数据段
}Heap;//函数声明-----------------------------------
//创建堆
extern Heap* HeapCreate();
//销毁堆
extern void HeapDestroy(Heap**);
//插入数据
extern void HeapPush(Heap**, DATATYPE);
//删除数据
extern void HeapPop(Heap**); 然后是 heap.c
#include heap.h//创建堆
Heap* HeapCreate()
{//创建堆空间Heap* heap (Heap*)malloc(sizeof(Heap) sizeof(DATATYPE) * 4);//创建结果检查if (!heap){fprintf(stderr, Malloc Fail\n);return NULL;}//初始化储存记录heap-size 0;heap-capacity 4;return heap;
}//销毁堆
void HeapDestroy(Heap** heap)
{//堆地址有效性检查if (!heap || !*heap){fprintf(stderr, Heap Address NULL\n);return;}//销毁堆空间free(*heap);*heap NULL;
} 这次就不每一步都测试了构建过程中可以自行测试。所以只需要在 main.c 中写入 include 头文件和 main 函数的壳即可
#include heap.hint main()
{return 0;
}
3、堆的数据操作 由于堆的特性主要只涉及增加数据及删除数据两个功能查找和修改在堆的操作上没有意义。此外本节的全部代码均写在 heap.c 之中。
3.1、插入数据 插入数据实际上是对顺序表的尾插但是尾插之后的堆很可能不符合堆的定义因此尾插之后还需对堆进行调整。调整步骤是不断地将插入的数据与父节点进行比较如果不符合大堆或者小堆的规律则互换。 这种操作称作向上调整也叫做上滤。以下是上滤操作的代码由于只在 heap.c 中调用用 static 修饰比较好。
//上滤
static void HeapFilterUp(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return NULL;}//获取初始父节点子节点下标size_t child heap-size - 1;size_t parent (child - 1) / 2;while (child ! 0){//如果不满足堆的条件if (heap-data[child] COMPARE heap-data[parent]){//向上交换数据DATATYPE tempData heap-data[child];heap-data[child] heap-data[parent];heap-data[parent] tempData;//计算新的父子节点下标child parent;parent (parent - 1) / 2;}else{break;}}
} 上滤函数中有两个比较容易坑的点首先是循环条件应该是子节的位置作为判断依据当子节点下标为 0 时说明已经到根节点了至此中断循环。此外当交换到某个位置时已经满足堆的特性记得中断循环。 完成上滤函数之后就可以开始写插入数据的函数主体了
//插入数据
void HeapPush(Heap** ptr_heap, DATATYPE data)
{//堆地址有效性检查if (!ptr_heap || !*ptr_heap){fprintf(stderr, Heap Address NULL\n);return;}//空间不足则扩容if ((*ptr_heap)-size (*ptr_heap)-capacity){Heap* tempHeap NULL;while (!tempHeap){tempHeap (Heap*)realloc(*ptr_heap, sizeof(Heap) sizeof(DATATYPE) * (*ptr_heap)-capacity * 2);}*ptr_heap tempHeap;(*ptr_heap)-capacity * 2;}//数据插入堆尾(*ptr_heap)-data[(*ptr_heap)-size] data;(*ptr_heap)-size;//上滤HeapFilterUp(*ptr_heap);
}
3.2、删除数据 这部分有点像由顺序表构建的队列 FIFO 属性。堆删除数据总是删除根节点。但是删除根节点后并不能如队列般将后面的元素往前挪原因如下图 因为堆的顺序与队列的顺序不一样既然是堆则不能以队列的方式挪动数据。 堆删除数据的常规的方式是将最后一个节点覆盖到根节点然后将 size - 1 。之后与上滤类似堆挪动数据的方式称为下滤或向下调整。过程是先比较两个子节点的大小如果是大堆则取较大的子节点再以较大的子节点与父节点比较如果不符合堆的特性则两者互换一直到叶节点。具体看下图例子。 根据这个思路先凹一个下滤函数
//下滤
static void HeapFilterDown(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return NULL;}//获取初始父节点子节点下标size_t parent 0;size_t child 1;while (child heap-size){//将左右两个子节点中数据较大值的节点下标赋予childif (child 1 heap-size heap-data[child 1] COMPARE heap-data[child]){child;}//如果不满足堆的条件if (heap-data[child] COMPARE heap-data[parent]){//向下交换数据DATATYPE tempData heap-data[child];heap-data[child] heap-data[parent];heap-data[parent] tempData;//计算新的父子节点下标parent child;child child * 2 1;}else{break;}}
} 刚才写完上滤函数之后写下滤函数最容易入一个坑就是循环条件以父节点下标是否超过数据个数作判定但当父节点为叶节点时子节点下标便已经超过数据个数了。当然也可以以父节点是否有子节点判定但本质上这还是判定子节点。 此外还有一个坑时刻需要注意如果父元素存在左子节点不一定存在右子节点因此还需要对右子节点的下标是否超过数据个数作判定。 下滤函数完成后删除数据自然信手拈来
//删除数据
void HeapPop(Heap** ptr_heap)
{//堆地址有效性检查if (!ptr_heap || !*ptr_heap){fprintf(stderr, Heap Address NULL\n);return;}//空堆直接返回if ((*ptr_heap)-size 0){fprintf(stderr, Empty Heap\n);return;}(*ptr_heap)-data[0] (*ptr_heap)-data[(*ptr_heap)-size - 1];(*ptr_heap)-size--;//空间过剩则回收if ((*ptr_heap)-size (*ptr_heap)-capacity / 2 (*ptr_heap)-capacity 4){Heap* tempHeap NULL;while (!tempHeap){tempHeap (Heap*)realloc(*ptr_heap, sizeof(Heap) sizeof(DATATYPE) * (*ptr_heap)-capacity / 2);}*ptr_heap tempHeap;(*ptr_heap)-capacity / 2;}//下滤HeapFilterDown(*ptr_heap);
} 这里还多加了回收多余空间的语句这步可以省略。因为堆的使用往往是一次性的它不是用来长久保存数据的更像是辅助其他算法的一种临时结构所以用过之后即销毁就没必要中途回收空间了。
3.3、其他功能 这部分功能可有可无这里仅展示代码当然也可以根据自己需要另外添加其他功能。
//获取堆顶数据
DATATYPE HeapGetData(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return -1;}//空堆直接返回if (heap-size 0){fprintf(stderr, Empty Heap\n);return -2;}return heap-data[0];
}//打印堆顶数据
void HeapPrint(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return;}//空堆直接返回if (heap-size 0){fprintf(stderr, Empty Heap\n);return;}printf(DATAPRT , heap-data[0]);
}//打印堆
void HeapPrintAll(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return;}//空堆直接返回if (heap-size 0){fprintf(stderr, Empty Heap\n);return;}int enterSite 0;for (int i 0; i heap-size; i){printf(DATAPRT , heap-data[i]);if (enterSite i){printf(\n);enterSite enterSite * 2 2;}}
} 最后别忘了在 heap.h 中加入声明
//获取堆顶数据
extern DATATYPE HeapGetData(Heap*);
//打印堆顶数据
extern void HeapPrint(Heap*);
//打印堆
extern void HeapPrintAll(Heap*);
4、堆排序
4.1、测试 堆最常见的作用便是堆排序了。因为堆的特性是根节点的数据是整个堆的最大值或者最小值而且下滤的效率比很多排序方法都高。刚好上面完成的堆结构还没进行测试所以这里以堆排序作测试。 main.c 中 main 函数补充如下
int main()
{//堆排序测试DATATYPE src[30] { 25,73,60,108,104,336,457,90,668,732,102,1,752,262,776,538,410,442,962,228,873,656,260,18,24,733,520,1414,339,439 };DATATYPE dest[30] { 0 };//建堆Heap* heap HeapCreate();//将src中的元素入堆for (int i 0; i 30; i){HeapPush(heap, src[i]);}//堆排序for (int i 0; i 30; i){dest[i] HeapGetData(heap);HeapPop(heap);}//输出排序前后结果printf(\n排序前 );for (int i 0; i 30; i){printf(%d , src[i]);}printf(\n排序后 );for (int i 0; i 30; i){printf(%d , dest[i]);}//销毁堆HeapDestroy(heap);return 0;
} 调试得到结果 就此测试完成。
4.2、优化思路 实际上堆排序上述方式有点拖沓了。由于堆往往用后即毁所以在进入排序步骤时不再另外创建数组二十直接在堆中操作。此时堆的结构虽然被破坏了但都到这一步了基本面临销毁在销毁前加以利用还能节省空间。 上述思路的堆排序与删除数据仅有一点点区别在于排序时是将根节点与最末尾节点进行互换而非覆盖。流程如下图 因此只需要把删除数据的函数改改
//堆排序
void HeapSort(Heap* heap)
{//堆地址有效性检查if (!heap){fprintf(stderr, Heap Address NULL\n);return;}//空堆直接返回if (heap-size 0){fprintf(stderr, Empty Heap\n);return;}//排序while (heap-size){//交换头尾数据DATATYPE temp heap-data[0];heap-data[0] heap-data[heap-size - 1];heap-data[heap-size - 1] temp;heap-size--;//下滤HeapFilterDown(heap);}
} 别忘了在 heap.h 中声明
//堆排序
extern void HeapSort(Heap*); 之后重写 main 函数
int main()
{//堆排序测试DATATYPE src[30] { 25,73,60,108,104,336,457,90,668,732,102,1,752,262,776,538,410,442,962,228,873,656,260,18,24,733,520,1414,339,439 };//建堆Heap* heap HeapCreate();//将src中的元素入堆for (int i 0; i 30; i){HeapPush(heap, src[i]);}//堆排序HeapSort(heap);//重新指定下size不然打印不出来heap-size 30;//打印HeapPrintAll(heap);//销毁堆HeapDestroy(heap);return 0;
} F5 走起 结果正确。完事
4.3、衍生 TopK 算法 堆除了排序之外还可用于解决 TopK 问题。首先什么是 TopK 一句话解释 TopK 就是取数据列表中最大或者最小的前 K 个数据。回想堆排序的过程HeapSort 函数中的 while 循环 n 次是排序 n1 个数据列表中的最值那么是否可以理解成堆排序实际上就是 K 等于数据个数 -1 的 TopK 算法 换个方式说堆排序是对所有节点进行排序而 TopK 只需排序前 K 个节点即可也就是说假设数据个数是 n 堆排序是对堆进行 n-1 次首尾互换后下滤操作而 TopK 则是执行 K-1 次首位互换后下滤的操作。其中K ≤ n 。 改改 HeapSort 函数就行了所以这里补贴代码了各位可以自行尝试。本篇至此结束。
