茂名网站建设教,青岛网站制作seo,wordpress发邮件更新,美食网站的建设开题报告文章目录 前言1. 堆1.1 堆的概念1.2 堆的分类 2. 堆的实现2.1 堆的结构体设置2.2 堆的初始化2.3 堆的销毁2.4 添加数据到堆2.4.1 向上调整算法 2.5 从堆中删除数据2.5.1 “向下调整”算法 2.6 堆的其它各种方法接口函数 3. 堆排序3.1 堆排序的代码实现 4. TOP-K问题… 文章目录 前言1. 堆1.1 堆的概念1.2 堆的分类 2. 堆的实现2.1 堆的结构体设置2.2 堆的初始化2.3 堆的销毁2.4 添加数据到堆2.4.1 向上调整算法 2.5 从堆中删除数据2.5.1 “向下调整”算法 2.6 堆的其它各种方法接口函数 3. 堆排序3.1 堆排序的代码实现 4. TOP-K问题4.1 什么叫TOP-K4.2 TOP-K问题求解的思路4.3 TOP-K问题的代码实现 前言
在我们学习完树和二叉树的一些基本概念和性质之后我只是简单的讲解了一下树的创建方式我们还并未讲二叉树的一些应用。那么在本文中我就会讲二叉树的应用——“堆”以及用对这个数据结构来实现堆数组进行排序的功能。这个就是大名鼎鼎的堆排序。
我还会针对堆排序给大家再次拓展一个大家在以后编程的道路上会经常的遇到的一个实际问题就是在一大堆数据中找出最大或最小的前几个数这个问题的本质就是堆排序我们也将这种问题称为TOP-K问题。至于它是怎么实现的请大家接着往下看 1. 堆
1.1 堆的概念
我在这里不想给大家讲官方的定义就直接给大家以一种更好理解的讲解。
堆其实就是一棵完全二叉树。但是这棵完全二叉树得满足一些性质
性质1堆中某个结点的总是不大于或不小于其父节点的值性质2堆总是一颗完全二叉树。(这个我们提到过了)
所以我们就记住以上两个性质如果都符合了那你就可以说这是堆。
由性质1就可以引出堆的两种类型。
1.2 堆的分类
堆分为两种
大堆大根堆首先它得是一棵完全二叉树其次它的某一个节点都不大于其父节点(小于或等于其父节点)。这个就是大堆的玩法。小堆小根堆首先它得是一棵完全二叉树其次它的某一个节点都不小于其父节点(大于或等于其父节点)。这个就是小堆的玩法。
还记得吗完全二叉树可以使用顺序表来实现这个是得益于完全二叉树的特性决定的。既然堆也是一棵完全二叉树那么我们也就可以用类似于顺序表这种物理结构(顺序存储)来进行堆的实现。
在这里先给大家一幅图感受大堆和小堆在逻辑结构和物理结构的模样帮助大家更好的理解堆这个数据结构: 2. 堆的实现
讲完堆的基本概念之后我就要详细的给大家讲讲堆是怎样用代码实现的内容很丰富希望大家能够好好看
2.1 堆的结构体设置
我们在之前讲过了堆是一棵完全二叉树我们可以用顺序表来实现。那我们就可以这样定义堆的结构体
//对int进行起别名是为方便代码的后期维护
typedef int HeapDataType;
typedef struct Heap
{HeapDataType* a;int size; //记录申请动态空间中有效的数据个数int capacity; //记录空间大小
}Heap;
2.2 堆的初始化
我们在开始实现每一个数据结构的各接口操作之前我们都得为这个数据结构进行初始化这些都是一些老套路了。
void HeapInit(Heap* php)
{assert(php); //传进来的指针不能是空指针不要就会造成对空指针进行解引用的误操作php-a (HeapDataType*)malloc(sizeof(HeapDataType)*4);php-size 0;php-capacity 4; //因为我申请了4个HeapDataType类型大小的空间
}2.3 堆的销毁
有动态内存申请就必要要释放空间我们不能总是让操作系统来帮我们擦屁股我们得有意识的释放动态内存申请之后的空间这对于我们提升代码的能力是一种很好的帮助。
void HeapDestory(Heap* php)
{assert(php);free(php-arr);php-arr NULL;//养成好习惯php-size 0;php-capacity 0;
}2.4 添加数据到堆
这里我们只需要一个函数就行。
那这时有的读者就会提问了为什么不写一个头插数据的函数和一个尾插数据的函数而只需要写一个添加数据的函数即可 原因就是我们在之前反复提到堆是一棵特别的完全二叉树。那我们往这个堆中添加数据添加完数据之后这个数据结构也还是堆啊。那既然是堆就得满足堆的特性。 我们总不能把人家的东西给彻底玩坏了吧。 那不管是头插还是尾插甚至是在某个位置上插入数据在最后都得被调整到符合堆这个数据结构特点的位置上。这就会给我们一个感觉就是不论我在哪个位置上插入跟我直接插入数据效果是一样的。为此我们直接洗一个插入数据的函数即可。 上面的解释中提到了一个名词调整那到底怎样调整呢这个就是本文的核心所在怎么解决调整数据的问题。
2.4.1 向上调整算法
在讲如何调整数据使之再次成为堆之前我要给大家灌输一个思想这个思想也是很多人在刚开始学习堆时比较难以转换的。这个思想就是“看树不是树”。
什么意思呢 堆在逻辑上是一棵完全二叉树但是在物理结构上是顺序表。所以我们要想堆不过就是在内存中连续存储的数组罢了。 那基于这层思想我们向堆里面插入数据无非就是往数组中插入一个数据。插入完数据之后再进行数字位置之间的调整使这个数组再次成为堆。 这个就是本算法的核心思想。
那我们该如何调整数组中数字的位置使之成为堆呢 在开始讲之前我会结合以下的这棵完全二叉树进行讲解这里我拿大堆举例 可以看到它物理结构时候的样子那我们先插入一个数字看看改变之后的样子。 可以看到的一个规律就是我即使添加了一个数据之后仍有部分的子树仍然是遵循堆的玩法的。这就给我们提供了一个很重要的思考方向就是从把堆弄的不像堆的的那棵子树入手。可以从上面的图中看出“罪魁祸首”的那棵树在我们添加数据的那个节点直至它的祖先形成的类似于导线的样子。 讲了这么多就是让大家明白一个道理。为什么这个算法叫做向上调整是由它的操作决定的。则会个算法通过将添加的数据的不断地往上调整最终到达属于它的皇位之上。
那接下来我就得聊一聊怎么挪动的了。这里针对的是大堆。 可以看到的是挪动之前我们得先判断它是否需要挪动挪动到什么位置就停止 这个就必须要知道孩子节点与其父节点之间的值的大小关系了。 现在我告诉大家一个公式这个公式十分重要大家一定要理解性记忆 假设孩子结点叫做child父亲节点叫做parent。(这里的 child 和 parent 的值是数组的下标) parent (child - 1) / 2 left_child parent * 2 1 right_child parent * 2 2 倘若我们真的掌握了这三条公式我们就可以通过孩子结点的下标直接找到其父节点我们也可以根据父节点找到其对应的孩子节点。这两者可以相互被访问 ok有了以上的思路我们就开始写代码吧。
void HeapPush(Heap* php, HeapDataType x)
{if(php-size php-capacity){HeapDataType* tmp (HeapDataType*)realloc(php-a,sizeof(HeapDataType) * 2 * phph-capacity);if(tmp NULL){perror(realloc fail);return;}//成功扩容php-a tmp;php-capacity * 2;}php-a[size] x;php-size;//对插入的数据进行位置调整使之再次成为大堆得用到向上调整算法AdjustUp(php-a,php-size);
}void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType tmp *x;*x *y;*y tmp;
}//向上调整算法
void AdjustUp(HeapDataType* a,int child)
{int 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;}}
}ok我们代码就这样水灵灵的写出来了。那么我请大家思考一个问题我把while循环的额条件变为parent0可以吗 也许有的人会说这个好像可以吧。但事实上我不建议大家这么写。大家不妨思考一下当parent变为0时循环条件成立进入循环执行循环体。当执行到parent (child - 1) / 2这条语句时parent的值是0为此它还会再一次进入循环。但不会出现死循环的情况因为if条件已经不满足了。 为此这里还是建议大家写child0这个判断条件。 2.5 从堆中删除数据
讲完了添加数据到堆的操作之后肯定还要再讲它的孪生兄弟从堆中删除数据。
它的思想跟添加数据的思想大部分是一致的这里我就不再讲多余的部分了。直接进入最核心的部分我们该在哪个位置删除数据删除完数据之后父亲结点和孩子节点的大小关系肯定就会混乱了那我们该怎么调整
这些问题在下面我都会给大家一一讲解睁大眼睛不要错过了哦
首先我们先解决第一个问题该删除数组上哪个位置上的数据 有的不假思索的就会说删除数组中最后一个位置上的数据但是这样删除数据有意义吗这个是我们要思考的问题。从逻辑角度上看好像对整棵树没有什么影响啊。确实没有影响删除这种位置上的数据是没有任何意义的 既然要玩我们就玩大的删掉根节点。这就好比在一个黑帮中老二觊觎老大的位置狠不得找个机会做掉老大总而自己主管整个黑帮。老三肯定也是想把老二做掉让自己走上更高的位置。这个道理就类似于堆的删除操作背后的含义。 到这里我们就理解了第一个问题要删除数据就删除堆中的根节点。
接下来我们就得解决第二个问题。那就是删除完数据之后父亲结点和孩子节点的大小关系肯定就会混乱了那我们该怎么调整 这个问题就好比有一天老二真的把老大给做掉了但是老二肯定得收买黑帮成员里面的人心支持他做老大。 下面我画一幅图给大家来一个直观的感受。 这个时候就要在给大家介绍另一个算法“向下调整”。
2.5.1 “向下调整”算法
事先说明一个重要的点在使用这个算法之前必须得确保根节点的左右子树都得是堆。
想要删除根节点的数据我们可以将根节点数据与数组中最后一个位置上数字交换值或则是直接覆盖。这里简单一点就直接将最后位置的值赋值给根节点这就相当于将根节点进行删除了。 那下一步我们就得调整各数字的位置了。用得算法就是“向下调整”。
那该怎么向下调整呢 首先我们知道了一个条件根节点的左右子树还是一个堆。那我们只需要将根节点(父节点)与它的左右孩子节点的值作比较如果比左右孩子结点值大的那个更小的话那就交换它们的值。如果都比这两孩子结点都大的话那就不用调整位置了。 根据以上的思路我们就来写写代码。
void HeapPop(Heap* php)
{assert(php php-size ! 0);php - size--;//向下调整算法Adjust(php-arr,php-size,0);
}void AdjustDown(HeapDataType* a,int n,int parent)
{//相比较左右孩子结点的值选取其中最大的那个//这里我使用假设法先假设左孩子的值大于右孩子的值。这样就可以避免设置多余的变量int child parent * 2 1; //这个上面提到过的公式while(child n){if(child 1 n a[child] a[child 1]){child;}//比较完左右孩子大小之后就要跟父节点进行大小的比较了if(a[parent] a[child]){//说明得交换值了Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}到这里向下调整的算法也将讲完了希望大家能够好好的消化。
之后一些堆的方法接口的就比较简单了我就一次性给大家写代码即可。
2.6 堆的其它各种方法接口函数
//判断堆是否为空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0 ? true : false;
}//计算堆的大小
int HeapSize(Heap* php)
{assert(php);return php-size;
}//查看堆的根节点的值
HeapDataType HeapTop(Heap* php)
{assert(php !HeapEmpty(php));return php-a[0];
}好了到这里我们就能完整的实现一个堆了。
那接下来我们就来讲一下堆排序 3. 堆排序
堆排序顾名思义就是利用堆这个数据结构对数据进行升序/降序排序。
回顾一下我们学过的数据结构从顺序表到链表、栈、队列以及我们现在学的堆。堆这个数据结构有很强烈的现实意义因为它能给我们的数据进行排序而且效率是目前效率最高的在没有学排序算法之前。
那么我们如何用堆进行排序呢我先给大家一个场景先让大家去想
void HeapSort(int* a,int n)
{//怎么实现
}int main()
{int a[] {5,2,3,7,1,9,8,10,6,4};//堆排序HeapSort(a,10);
}3.1 堆排序的代码实现
现在我来揭晓答案:
void HeapSort(int* a,int n)
{//向上调整的时间复杂度为O(N*logN)/*for(int i 0; i n; i){AdjustUp(a,i);}*///向下调整的效率更高时间复杂度为O(N)for(int i (n - 1 - 1) / 2; i 0 ; i--){AdjustDown(a,n,i);}//这一步就是将最大的数字置换到数组的尾部。最后再进行调整for(int end n - 1; end 0 ; end--){Swap(a[end],a[0]);AdjustDown(a,end,0);}
}int main()
{int a[] {5,2,3,7,1,9,8,10,6,4};//堆排序HeapSort(a,10);for(int i 0 ; i 10 ; i){printf(%d ,a[i]);}
}4. TOP-K问题
4.1 什么叫TOP-K
顾名思义就是求前K个数值。可能是最大的前K个也可能是最小的前K个。
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
4.2 TOP-K问题求解的思路
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆前k个最小的元素则建大堆 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
4.3 TOP-K问题的代码实现
这里我们就用文件操作生成10000个数字每个数字的范围是在0~999之间。找出这10000个数字最大的前10个打印出来。
void CreatData()
{srand((unsigned int)time(NULL));FILE* fin fopen(data.txt,w);if(fin NULL){perror(fopen fail);return;}for(int i 1; i10000; i){fprintf(fin,%d\n,rand()%1000);}fclose(fin);fin NULL;
}void PrintTopK(const char* filename, int k)
{FILE* fout fopen(filename,r);if(fout NULL){perror(fopen fail);return;}int* topk (int*)malloc(sizeof(int) * k);for(int i 0; i k; i){fscanf(fout,%d,topk[i]);}for(int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(topk,k,i); //这里如果是要选最大的话调整为小根堆。反之调整为大根堆。}int val 0;int ret fscanf(fout,%d,val);while(ret ! EOF){if(topk[0]val){topk[0] val;AdjustDown(topk,k,0);}ret fscanf(fout,%d,val);}//最后打印结果while(k){printf(%d ,topk[k-1]);k--;}fclose(fout);fout NULL;free(a);a NULL;
}大家为了方便测试可以在data.txt这个文本文件中将其中10个值改为都大于1000的这样的话测试的结果就显而易见了。
测试结果
到这里关于堆的内容就已经全部讲完了
如果觉得本文写还不错的话麻烦给偶点个赞吧
