公司网站一定要域名吗,平顶山市湛河区建设局网站,网站和官网有区别吗,wordpress idstore目录 一、堆1. 堆的存储定义2. 初始化堆3. 销毁堆4. 堆的插入向上调整算法 5. 堆的删除向下调整算法 6. 获取堆顶数据7. 获取堆的数据个数8. 堆的判空 二、Gif演示三、 堆排序1. 堆排序(1) 建大堆(2) 排序 2.Topk问题 四、完整代码1.堆的代码Heap.cHeap.htest.c 2. 堆排序的代码… 目录 一、堆1. 堆的存储定义2. 初始化堆3. 销毁堆4. 堆的插入向上调整算法 5. 堆的删除向下调整算法 6. 获取堆顶数据7. 获取堆的数据个数8. 堆的判空 二、Gif演示三、 堆排序1. 堆排序(1) 建大堆(2) 排序 2.Topk问题 四、完整代码1.堆的代码Heap.cHeap.htest.c 2. 堆排序的代码 前言: 什么是堆呢 堆Heap是一种数据结构它是 一种特殊的二叉树 其中父节点的键值总是大于或等于或小于或等于其任何一个子节点的键值。这意味着在堆中根节点具有最大或最小键值。 堆一般是数组数据看做一棵完全二叉树 完全二叉树的逻辑结构 大堆 任意一个父结点 大于等于 子结点 小堆 任意一个父结点 小于等于 子结点 数组存储完全二叉树
一、堆
1. 堆的存储定义
因为存储结构这里使用动态数组的形式来存放数据。但是也要注意其中的逻辑结构是完全二叉树。定义一个指针指向动态数组定义存储堆的容量capacity记录堆中的数据的个数size
代码
typedef int HPDataType;
typedef struct Heap
{HPDataType* a; //指向动态数组int capacity; //堆的容量int size; //堆中数据个数
}Heap;2. 初始化堆
类似顺序表的初始化
代码
//初始化堆
void InitHeap(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity 0;hp-size 0;
}3. 销毁堆
避免内存泄漏
代码
//销毁堆
void DestroyHeap(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity hp-size 0;
}4. 堆的插入
重点 在堆的插入前我们需要注意的就是首先判断其容量然后使用realloc给数组分配空间 分配空间后把数据插入堆。但是数据在插入堆时由于堆一般分为大根堆和小根堆所以这里使用的大根堆。 大堆父结点的值大于等于其孩子结点的值 但是数据的值不能确定这个时候就需要我们使用 堆的向上调整算法
向上调整算法
在数组的末端插入元素进行与其父结点进行比较大堆的情况下如果其孩子结点的值大于父亲结点的值时把插入的数据向上调整向上调整的方法是:把插入的数据与其父结点进行交换交换后继续判断是否还需要向上调整。(使用向上调整算法的条件是前面结点的树是构成堆的)
这里是使用的是数组所以当插入元素时在数组的末端进行插入数据
物理存储 逻辑存储情况
在插入的数据时我们就需要考虑一下 1. 当插入的孩子结点的值大于其父亲结点的值时就向上调整 思路 首先是根据孩子结的下标找父结点的下标孩子结点下标-1/2 父结点下标因为可能调整所以将判断条件放到循环里面(当然也可以用递归)在循环里面切记一定要及时更新当前孩子结点的下标和父结点的下标孩子结点的值大于父结点的值就向上调整否则就跳出循环。当孩子结点的下标到0时向上调整完成循环结束。 2. 当小于等于时不需要调整 代码
//向上调整
void AdjustUp(HPDataType * a,int child)
{//先找到父结点的下标int parent (child - 1) / 2;while (child 0) //child等于0时说明已经调整ok了{if (a[child] a[parent]){swap(a[child], a[parent]);//可能会向上调整多次child parent;parent (parent - 1) / 2;}else {break;}}
}//堆的插入
void PushHeap(Heap* hp, HPDataType x)
{assert(hp);//堆满判断if (hp-capacity hp-size) {int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity;HPDataType* tmp (HPDataType*)realloc(hp-a,sizeof(HPDataType)*newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}hp-a tmp;hp-capacity newcapacity;}//堆元素的插入hp-a[hp-size] x;hp-size;//堆的向上调整AdjustUp(hp-a,hp-size-1);
}调试查看一下数据存储情况
5. 堆的删除
堆中元素的删除发现直接删除尾结点是简单的(size减一即可)但是一般堆删除元素都是删除的头结点。 直接删除头结点时发现逻辑结构上变成了两棵树这样直接删除头结点的方法不推荐。 交换结点再删除 头尾结点交换后再删除尾结点然后头结点使用堆的向下调整算法调堆。 使用前提就是当进行交换的时候保证左右仍是堆。第一个结点与最后一个结点的值交换后向下调整。
向下调整算法
这里调的堆是大堆根结点的值大于左右孩子结点的值
第一步找到第一个根结点的孩子结点这里使用假设法先让左孩子的值最大再进行判断左孩子还是右孩子的值是最大的找出大的。第二步与根结点进行比较大于根结点就交换。及时更新父结点和孩子结点的下标注意当孩子结点值都小于父亲结点值就跳出循环;循环结束条件孩子结点的下标大于数组最大的下标(就是孩子下标数组的个数childsize,大于等于时说明循环就结束了)。
过程 调整后 这样就完成堆头结点的删除。 还需要注意的就是
代码
//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先去找根结点的较大的孩子结点int child 2 * parent 1;//可能会向下调整多次while (childsize) {//这里使用假设法先假设左孩子的值最大//如果不对就进行更新if ((child1 size)a[child] a[child1]) {child;}//根结点与其孩子结点中的较大的一个进行交换if(a[child] a[parent]) {swap(a[child],a[parent]);//更新下标parent child;child 2 * parent 1;}else {break; //调完堆}}
}
//堆的删除
void PopHeap(Heap* hp)
{assert(hp);assert(hp-size0);//头尾交换swap(hp-a[0],hp-a[hp-size-1]);hp-size--;//向下调整AdjustDown(hp-a,hp-size,0);
}调试一下 上图中指向下标6其实有数据65的但是数组的下标有效范围在0-5
6. 获取堆顶数据
前提:堆得有数据 代码
//获取堆顶数据
HPDataType TopHeap(Heap* hp)
{assert(hp);assert(hp-size0);return hp-a[0];
}7. 获取堆的数据个数
代码
//获取堆的数据个数
int SizeHeap(Heap* hp)
{assert(hp);return hp-size;
}8. 堆的判空
代码
//堆的判空
bool EmptyHeap(Heap* hp)
{assert(hp);return hp-size 0;
}二、Gif演示
调堆演示
三、 堆排序
堆排序是一种选择排序。 堆排序可以从小到大进行排序(使用大堆)。Top k 问题取出最大的前k个值。
1. 堆排序
堆排序Heap Sort是一种基于完全二叉树的排序算法它通过将待排序的元素建成一个二叉堆。堆排序的时间复杂度为O(nlogn)它是不稳定排序算法。
堆排序的思路如下
以升序排序为例先建立一个大堆父节点的值大于子节点的值将待排序的元素都插入堆中。将堆顶元素最大值与堆末尾元素交换然后将堆的大小减1。对堆顶元素向下调整操作使得堆重新满足最大堆的性质。重复2-3步直到堆的大小为1。排序完成。
(1) 建大堆
使用 向下 调整算法来向上建堆使用向下调整算法把数组调成大堆 因为堆本身是一个完全二叉树假设一共有h层我们从第h-1层(即不是叶子结点的那一层开始) 因为是大堆根结点的值大于孩子结点的值从最下方使用向下调整来不断把较大的值来调到根节点。 注意虽然使用的是向下调整算法其实还是不断往上调整把大的值调到上面。 如图: 直到调整到第一层为止 建堆时间复杂度O(N)
//堆排序
void HeapSort(int* arr, int n)
{int i 0;//使用向下调整算法向上调整把大的值调到上方。for (i (n - 1 - 1) / 2; i 0;i--){//先找到数组最后端的父结点的下标//父结点的下标减一就是另一个//使用向下调整算法进行调整AdjustDown(arr,n,i);}
}当然也可以用向上算法进行向上建堆。
思路先让一个独自成堆然后尾插一个结点再进行与根结点进行比较大于根结点的值就交换。 但是这个使用向上调整算法向上建堆的时间复杂度为O(Nlog(N))
//向上调整算法进行堆排序
void HeapSort(int* arr, int n)
{int i 0;//先让第一个结点独自成堆//再一次尾增结点进行向上调整for (i 1; i n; i) {AdjustUp(arr,i);}
}(2) 排序
因为建成大堆后将堆顶元素最大值与堆末尾元素交换 //注意end 是从n-1开始的(数组最后一个元素的下标)int end n-1;while (end 0) {//swap end n-1 这表示下标swap(arr[0],arr[end]);//adjustdown 函数里面的end是元素的个数所以不是先--end//所以AdjustDown(arr,end,0);end--;}注意这里的end–,上述是从数组最后一个元素下标n-1 开始。堆的首元素与尾元素交换完后接着就是堆的个数减1然后下进行向下调整。这里的end–放在了最后。因为AdjustDown中的第二个参数是传的是堆的大小正好数组下标n-1 , 堆由n减一也是 n -1。
下方给出了 end 从n 开始的优化,但是可读性就会下降
void HeapSort(int* arr, int n)
{int i 0;//先建成一个大堆for (i (n - 1 - 1) / 2; i 0;--i) {AdjustDown(arr,n,i);}//堆顶元素与堆尾元素进行交换进而把大的元素放到后面int end n;while (end 0) {swap(arr[--end],arr[0]);AdjustDown(arr,end,0);}
}2.Topk问题
topk问题例如在10000个数据排名中找出前10或者在10000个数中找出最大的前10个
这里我们就以在10000个数中找出最大的前10(k 10)个为例
首先应先准备数据,随机生成10000个数(注意srand函数只能生成30000多个随机数) 核心思想 建一个可以存储k个数据的小堆。先把文件数据前10个数据读取到小堆中(进行向下调成小堆)然后再把文件中的其他数据一个一个读出与小堆的根结点的值进行比较如果大于小堆的根结点就进放入堆中然后进行向下调堆。
//创建数据
void Createdata()
{int n 10000;srand((unsigned)time(0));const char* file data.txt;FILE* fin fopen(file,w);if (fin NULL){perror(fopen error);return;}for (int i 0; i n;i){int x (rand() i) % 100000;//把随机生成的数据写到fin文件中去fprintf(fin,%d\n,x);}fclose(fin);
}void PrintTopK(int k)
{//从文件中读出数据const char* file data.txt;FILE* fout fopen(file,r);if (fout NULL){perror(fout error);return;}//将数据读出到容量为k的动态数组中int* arr (int*)malloc(sizeof(int)*k);if (arr NULL){perror(malloc error);exit(-1);}//先把前k个数据放入数组中for (int i 0; i k; i){//将数据读到数组中fscanf(fout,%d,arr[i]);//放数据的同时进行建堆AdjustUp(arr,i);}int x 0;//当文件里面的数据读完后会返回EOFwhile (fscanf(fout, %d, x) ! EOF) {//当从文件拿出的数据大于小堆中的数据时//将数据放到小堆中//并使用向下调整//这样每次来的比较大的数据就可以放到小堆中if (x arr[0]) {arr[0] x;AdjustDown(arr,k,0);}}//打印数据for (int i 0; i k;i) {printf(%d ,arr[i]);}fclose(fout);}四、完整代码
1.堆的代码
Heap.c
#include Heap.h//初始化堆
void InitHeap(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity 0;hp-size 0;
}//销毁堆
void DestroyHeap(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity hp-size 0;
}//交换两个数
void swap(HPDataType* s1,HPDataType* s2)
{HPDataType tmp *s1;*s1 *s2;*s2 tmp;
}
//向上调整
void AdjustUp(HPDataType * a,int child)
{//先找到父结点的下标int parent (child - 1) / 2;while (child 0) //child等于0时说明已经调整ok了{if (a[child] a[parent]){swap(a[child], a[parent]);//可能会向上调整多次child parent;parent (parent - 1) / 2;}else {break;}}
}//堆的插入
void PushHeap(Heap* hp, HPDataType x)
{assert(hp);//堆满判断if (hp-capacity hp-size) {int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity;HPDataType* tmp (HPDataType*)realloc(hp-a,sizeof(HPDataType)*newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}hp-a tmp;hp-capacity newcapacity;}//堆元素的插入hp-a[hp-size] x;hp-size;//堆的向上调整AdjustUp(hp-a,hp-size-1);
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先去找根结点的较大的孩子结点int child 2 * parent 1;//可能会向下调整多次while (childsize) {//这里使用假设法先假设左孩子的值最大//如果不对就进行更新if ((child1 size)a[child] a[child1]) {child;}//根结点与其孩子结点中的较大的一个进行交换if(a[child] a[parent]) {swap(a[child],a[parent]);//更新下标parent child;child 2 * parent 1;}else {break; //调完堆}}
}
//堆的删除
void PopHeap(Heap* hp)
{assert(hp);assert(hp-size0);//头尾交换swap(hp-a[0],hp-a[hp-size-1]);hp-size--;//向下调整AdjustDown(hp-a,hp-size,0);
}//获取堆顶数据
HPDataType TopHeap(Heap* hp)
{assert(hp);assert(hp-size0);return hp-a[0];
}//获取堆的数据个数
int SizeHeap(Heap* hp)
{assert(hp);return hp-size;
}//堆的判空
bool EmptyHeap(Heap* hp)
{assert(hp);return hp-size 0;
}Heap.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a; //指向动态数组int capacity; //堆的容量int size; //堆中数据个数
}Heap;//初始化堆
void InitHeap(Heap* hp);//销毁堆
void DestroyHeap(Heap* hp);//堆的插入
void PushHeap(Heap* hp, HPDataType x);//堆的删除
void PopHeap(Heap*hp);//获取堆顶数据
HPDataType TopHeap(Heap* hp);//获取堆的数据个数
int SizeHeap(Heap* hp);//堆的判空
bool EmptyHeap(Heap* hp);test.c
#include Heap.hvoid Test1()
{Heap hp;InitHeap(hp);PushHeap(hp,49);PushHeap(hp,65);PushHeap(hp,34);PushHeap(hp,25);PushHeap(hp,37);PushHeap(hp,27);PushHeap(hp,19);//删除65PopHeap(hp);//printf(堆的个数%d\n,SizeHeap(hp));//while (!EmptyHeap(hp)) //{// printf(%d-, TopHeap(hp));// PopHeap(hp);//}DestroyHeap(hp);//27,19,34,65,49,25,37
}
int main()
{Test1();return 0;
}2. 堆排序的代码
//堆排序
void HeapSort(int* arr, int n)
{int i 0;//使用向下调整算法向上调整把大的值调到上方。for (i (n - 1 - 1) / 2; i 0;i--){//先找到数组最后端的父结点的下标//父结点的下标减一就是另一个//使用向下调整算法进行调整AdjustDown(arr,n,i);}//进行排序//因为是大堆所以根结点的值是最值//把最值与堆的最后一个结点进行交换//再把交换后的根节点进行向下调整//然后堆的大小减一//注意end 是从n-1开始的(数组最后一个元素的下标)int end n-1;while (end 0) {//swap end n-1 这表示下标swap(arr[0],arr[end]);//adjustdown 函数里面的end是元素的个数所以不是先--end//所以AdjustDown(arr,end,0);end--;}
}
