衡水哪家制作网站好,wordpress能恢复数据库吗,网站建设与推cctv-10,润滑油手机网站模板文章目录 一、堆排引入之使用堆排序数组二、真正的堆排1.向上调整算法建堆2.向下调整算法建堆3.向上和向下调整算法建堆时间复杂度比较4.建堆后的排序4.堆排序和冒泡排序时间复杂度以及性能比较 三、Top-K问题 一、堆排引入之使用堆排序数组 在了解真正的堆排之前#xff0c;我… 文章目录 一、堆排引入之使用堆排序数组二、真正的堆排1.向上调整算法建堆2.向下调整算法建堆3.向上和向下调整算法建堆时间复杂度比较4.建堆后的排序4.堆排序和冒泡排序时间复杂度以及性能比较 三、Top-K问题 一、堆排引入之使用堆排序数组 在了解真正的堆排之前我们先来试着使用我们写过的堆来模拟一下数组的排序堆的定义和实现在上一篇文章已经讲过还没有学过堆可以参考【初阶数据结构和算法】二叉树顺序结构—堆的定义与实现(附源码) 这里我们直接开讲我们之前说过堆除了是一个完全二叉树之外还有一个重要特性就是它的每一颗子树的根节点都是整颗子树的最大或最小值那么一提到它的这个特性我们可以想到什么呢 是不是我们会自然而然的想到使用堆进行排序在讲解使用堆进行排序之前说明一下一般我们排序都是对数组进行排序所以我们要先将数组中的内容先全部入堆处理完之后再放入数组中 那么是不是我们每次使用堆进行排序必须先写一个堆把数组中的内容放入堆排完序之后再把数据放回数组呢其实并不会这个问题到后面真正的堆排部分就知道了现在先暂时留留悬念 现在我们还是继续刚刚的思路毕竟现在属于堆排的引入部分我们要先知道用堆进行排序的大致逻辑后才能将真正的堆排理解透彻 当前的思路就是我们将数组中的数据放入堆中然后循环地取堆顶、出堆顶元素每取到一次堆顶就放回数组中直到堆为空这样我们每次都可以从当前堆中取到最值将它们依次放回数组自然就可以实现排序 接下来我们以升序为例来画个简图模拟一下我们上面的思路如下 根据上面的示意图我们大致了解了整个使用堆进行排序的过程可以发现确实可以使用堆来进行排序那么有了思路我们就开始动手写代码
//强调一下这里演示的不是真正的堆排
//只是为了引出堆排写出的模拟思路
void HeapSort(int* arr, int n)
{HP hp;HPInit(hp);size_t i 0;for (i 0; i n; i){//将数组中的数据放入堆中HPPush(hp, arr[i]);}i 0;while (!HPEmpty(hp)){//堆不为空就取堆顶放入数组中int top HPTop(hp);arr[i] top;HPPop(hp);}HPDestroy(hp);
}void Print(int* arr, int n)
{for (size_t i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}int main()
{int arr[] { 4,10,24,19,1,6 };int sz sizeof(arr) / sizeof(arr[0]);HeapSort(arr, sz);Print(arr, sz);return 0;
}那么我们来看看上面代码的运行结果看看能否排序成功 可以看到最后我们成功将数组排成了升序但是我们也反复强调这并不是真正的堆排只是引出堆排的一种思路因为我们如果直接使用堆这种数据结构进行排序的话每次都必须写一个堆来辅助排序太麻烦了 所以真正的堆排是借助了堆的算法思想直接对数组进行调整而不需要专门写一个堆来辅助完成堆排那么接下来我们就来学习一下真正的堆排
二、真正的堆排 真正的堆排并不是使用堆这种数据结构来实现排序而是借鉴了堆的算法思想可以让数组模拟为一个堆进行排序虽然实现可能麻烦一点点但是它的效率非常高等到我们和冒泡排序进行对比就知道了下面我们就开始正式学习 首先我们要对数组进行排序那么大概率我们会拿到一个乱序的数组我们需要通过调整将这个乱序的数组模拟成为一个堆因为堆的底层也是用数组存储的我们要是能让数组模拟成为一个堆就可以不必再写一个堆这样的数据结构辅助排序了 我们将一个乱序数组模拟成为一个堆的过程称为建堆建堆有两种思路当我们讲解完之后我们再来对比它们有什么区别
1.向上调整算法建堆 现在我们要对一个乱序的数组使用向上调整算法建堆我们之前讲过的向上调整算法都是建立在原本的堆上也就是在向上调整之前除了最后一个元素以外其它的元素已经构成一个堆了是在堆的基础上向上调整 而我们现在要对一个乱序的数组建堆也要沿用这种思想具体思路就是将一个乱序数组看作一颗完全二叉树默认从根节点开始将每一个节点都看作需要调整孩子节点都进行一次向上调整如果不懂可以直接看下面画的图 为什么说这样就可以让乱序数组成堆了呢我们可以仔细分析一下第一次将根当作要调整的节点时由于只有它一个节点所以默认它自己就能成一个堆 然后第二次将根的左孩子当作要调整的节点时就将根节点加左孩子这颗小的子树调整成了一个堆第三次将根的右孩子当作要调整的节点时就将根节点加左右孩子这颗子树调整成了一个堆如果不懂可以直接看下面画的图 这样一个节点一个节点地调整每调整一个节点就让这个节点和上面的节点成一个堆当我们将每个节点都这样调整一次后就能得到一个堆我们来画图理解一下(这里以建小堆为例) 根据上图的样例应该能更好地理解向上建堆的思想了这里我们总结一下规律向上建堆的本质就是从根节点开始每让一个节点向上调整一次就能使得这个节点和前面的节点构成的小子树成堆 那么是不是我们将所有节点都向上调整之后就能将整个乱序数组建成一个堆那么接下来有了思路我们就可以来写对应的代码了具体做法就是创建一个循环从根节点开始依次对每个节点进行向上调整如下
//向上调整建堆
for (int i 0; i n; i)
{AdjustUp(arr, i);
}是不是看起来很简单呢那么又是不是只能使用向上调整算法建堆呢其实还可以使用向下调整算法来建堆我们马上就来讲讲向下调整算法建堆 当然学到这里我们已经建好堆了如果想提前学一下将我们建好堆的数组进行最后的排序可以先看建堆后的排序没有看向下调整算法也不影响观看
2.向下调整算法建堆 在上面我们使用向上调整算法建堆了就是将每个节点都当作孩子来向上调整每调整一个节点这个节点和之前的节点构成的小子树就能构成堆到最后一个节点向上调整之后整颗树就成了堆 那么我们能不能将每个节点当作父节点都进行一次向下调整呢我们从最后一个节点往前开始向下调整这样每向下调整一个节点这个节点和之后的节点构成的小子树也能成堆到堆顶节点向下调整之后整颗树也就成了堆可以自行 但是我们其实可以对上面的思路进行优化因为最后一层的节点都是叶子节点它们都没有孩子自然就不能进行向下调整所以我们要找到从下至上的第一个可以作为父节点的节点 其实也不难想到这个节点就是最后一个节点的父节点最后一个节点的父节点一定是从下至上的第一个可以作为父节点的节点 那么有了思路之后我们就可以来直接写出代码了至于整个向下调整算法建堆的示例图可以自行去挑战一下只有自己能把整个过程画出来了之后才是真正懂了向下调整算法建堆那么这里我们直接给出代码
//向下调整算法建堆
//n-1是最后一个节点(n-1-1)/2是最后一个节点的父节点
for (int i (n - 1 - 1) / 2; i 0; i--)
{AdjustDown(arr, i, n);
}3.向上和向下调整算法建堆时间复杂度比较 我们先来简单看看一次向上调整和向下调整的时间复杂度按照最坏的情况来算一次向上或向下调整都要调整满二叉树的层数次我们之前说过二叉树的层次为log2(n1)所以我们可以得出一次向上或向下调整的时间复杂度为O(log N) 我们向上调整建堆和向上调整建堆的外层循环大致都是一个n所以我们猜测向上调整建堆和向上调整建堆的时间复杂度大致为O(N * log N) 那么它们之间是否就是没有区别呢随意使用哪个都可以吗其实并不是向上调整算法建堆的时间复杂度确实为O(N * log N)但是向下调整算法建堆的时间复杂度其实是O(N)要更快一些 那么是为什么呢这里我们给出计算向下调整算法建堆时间复杂度的证明过程需要用到高中学过的错位相减至于向上调整算法建堆的证明过程可以参照这个方式可以自行下去证明那么现在我们直接给出向下调整算法建堆时间复杂度的证明过程如下 根据上面的证明我们可以得出向下调整算法建堆的时间复杂度确实为O(N)而不是O(N * log N)向上调整算法建堆的证明可以自行参照实现一下最后结果为O(N * log N) 所以最后我们得出结论向下调整算法建堆优于向上调整算法建堆
4.建堆后的排序 当我们使用向上和向下调整算法建堆之后我们现在需要对它进行最后的排序具体的思路不难但是可能有些抽象需要我们细细分析画画图 首先在引入部分我们是利用现有的数据结构堆进行排序将堆顶取出放回数组再出堆顶数据直到堆为空但是现在我们只有一个成堆的数组该怎么操作呢 核心其实还是一样的我们可以在数组中模拟取堆顶数据出堆顶数据反复拿到最值具体方法就是 交换根节点和最后一个节点此时最后一个节点就是最大或最小的值随后对新的堆顶元素进行向下调整注意向下调整时要除开最后一个节点让剩下的节点继续成堆 然后就是交换根节点和倒数第二个节点此时倒数第二个节点就是第二大或第二小的值随后又对新的堆顶元素进行向下调整此时向下调整时要除开倒数第二个节点让剩下的元素继续成堆 随后重复进行以上步骤直到将整个数组排成有序可能这样纯文字不好描述我们来画图理解一下这里还是以小根堆为例 根据上图的演示我们应该能够猜到如果我们把后面的操作做完会发生什么应该会将整个数组排成降序因为每次都将当前堆的最小值往后面拿那么大的都在前面了小的都在后面的自然就成为了降序 那么我们如何把上面的功能写成代码呢这里的难点就是如何每次都调整和交换时都不去影响已经排序好的数据这里就直接给出思路 我们可以定义一个变量end作为下标来划分这个数组在end之前的节点是还未处理好的节点end指向的节点就是要交换的节点位置end之后的节点是已经挪动过的、处理好的节点如图 此时数组都是还未处理的节点让end指向最后一个节点处表示end处的节点是要交换的节点它之后还没有已经处理好的节点之前都是未处理的节点随后交换根节点和end位置的节点如图 然后将end作为向下调整时的堆中的数据个数那么就只会调整end位置之前的节点不会影响end位置的节点如图 那么有了整个建堆后的排序思路我们接下来就直接写出代码如下
int end n - 1;
while (end 0)
{Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;
}那么整个完整的堆排就已经完成了完整代码为
void HeapSort(int* arr, int n)
{//向上调整建堆/*for (int i 0; i n; i){AdjustUp(arr, i);}*///向下调整算法建堆//n-1是最后一个节点(n-1-1)/2是最后一个节点的父节点for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, n);}int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}
}我们来看看代码运行的结果 可以看到我们成功地将数组排成降序了我们这里最后再提示几点
我们建小堆会将数组排成降序建大堆会将数组排成升序因为最值都是放在最后的堆排的时间复杂度为O(N * log N)建堆的时间复杂度为O(N * log N)或O(N)建堆后的排序的时间复杂度为O(N * log N)所以总体下来堆排的时间复杂度大致为O(N * log N)由于我们将数组建堆后还是需要使用向下调整算法来进行最后的排序再加上向下调整算法建堆又更快所以在实现堆排时我们往往只写一个向下调整算法建堆和建堆后的排序都用它
4.堆排序和冒泡排序时间复杂度以及性能比较 那么现在我们新学了堆排这种排序方式我们来对比一下堆排和冒泡排序首先它们的时间复杂度一个为O(N * log N)一个为O(N^2) 我们来看看它们的差距到底有多大我们来写一个代码随机生成10万个整型数据看看最后它们分别用时多少代码如下
#include stdio.h
#include time.h
#include stdlib.hvoid TestOP()
{srand((unsigned int)time(NULL));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();HeapSort(a1, N);int end1 clock();int begin2 clock();BubbleSort(a2, N);int end2 clock();printf(HeapSort:%d\n, end1 - begin1);printf(BubbleSort:%d\n, end2 - begin2);free(a1);free(a2);
}int main()
{TestOP();return 0;
}为了保证测试出最真实的数据我们要把debug版本调成release版本然后运行代码我们来见证一下最后排序的结果如图 是不是特别惊讶呢整整10万个数据堆排只需要5毫秒而冒泡排序则需要7秒多差距达到了上千倍所以堆排其实是很快的是最优秀的几个排序算法之一至于其他的排序算法我们在后面还会介绍
三、Top-K问题 在解决TOP-K问题之前我们要了解TOP-K问题是什么它是求数据结合中前K个最⼤的元素或者最⼩的元素⼀般情况下数据量都⽐较⼤⽐如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 那么我们能不能对这些数据直接进行排序呢很明显是不现实的因为有一些TOP-K问题的数据量非常大我们不能都加载到内存中去排序效率也不高 所以我们要想一个办法让我们能够在内存被限制到很小的情况下也能找出大量数据结合中前K个最⼤的元素或者最⼩的元素那么到底怎么解决呢 我们现在来假设一个场景来辅助我们讲解假设要求我们只能开k个内存空间有10万个整型数据都存放在外存的磁盘文件上我们要找到磁盘文件中前K个最大的数这种情况下我们使用堆来解决 在我们着手来解决这个问题前我们要先把环境模拟出来就是要在我们当前目录下生成一个有10万个随机整数的文件这里直接给出造数据文件的函数代码这只是环境模拟不是重点重点是我们之后的TOP-K造数据函数代码如下
#include stdio.h
#include stdlib.h
#include time.hvoid CreateNDate()
{// 造数据int n 100000;srand((unsigned int)time(NULL));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) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}上面就是造数据的函数的代码了注意这个代码只需要运行一次就可以造出我们想要的文件随后注释掉就好了环境模拟好之后我们就进入真正的Top-K问题的解决了 首先我们要知道k是多少它最好由用户决定所以我们可以使用scanf来读取k接着我们就来详细聊聊解决Top-K问题的基本思路
⽤数据集合中前K个元素来建堆前k个最⼤的元素建⼩堆前k个最⼩的元素建⼤堆⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素 首先我们来解释为什么我们求前k个最⼤的元素建⼩堆比如当我们建好小堆后堆顶元素就是整个堆的最小值那么我们是不是就可以反推其它的元素都是比堆顶大的元素 那么我们就可以这样做先从文件读取k个数据放入堆中堆顶就是最小的数据然后再继续从文件中读取N-K个数据每读到一个数据就和堆顶元素做比较 如果这个数据比堆顶还小那么这个数据也肯定比堆里面其它的数据更小因为我们建的是一个小堆堆顶元素就是最小的比堆顶元素小就比整个堆中的所有元素小此时我们就可以不管这个元素了因为我们要找前K个最大的数 如果这个数据比堆顶大说明出现了一个较大的值得入堆的数据那么我们就把当前堆中的堆顶删掉让这个数据入堆然后再拿这个堆的堆顶和剩余元素比较重复上面的操作那么到最后这存放k个数据的堆一定就是前k个最大的数据 上面我们解释的是前k个最⼤的元素建⼩堆前k个最⼩的元素建⼤堆也是相同的原理可以按上面的思路自行推导一下这里就不再赘述 那么有了上面的思路我们可以直接写出求10万个数据中前k个最大值的代码如下
//找10万个数据中前k个最大的值
void TopK()
{FILE* fin fopen(data.txt, r);if (fin NULL){perror(fopen error);return;}int k 0;scanf(%d, k);//建小堆HP hp;HPInit(hp);int tmp 0;for (int i 0; i k; i){if (fscanf(fin, %d, tmp) ! EOF){HPPush(hp, tmp);}}while (fscanf(fin, %d, tmp) ! EOF){if (tmp HPTop(hp)){HPPop(hp);HPPush(hp, tmp);}}while (!HPEmpty(hp)){printf(%d , HPTop(hp));HPPop(hp);}HPDestroy(hp);fclose(fin);
}int main()
{//CreateNDate();TopK();return 0;
}在开始测试之前我们要再提醒一下我们现在并不知道文件中的最大值是多少不能验证代码的正确性所以我们打开这个数据文件修改或添加几个很大的值这里我选择添加100万和999999我们来看看代码能不能帮我们找到它们两个如图 可以看到我们成功在10个数据中找到了前2个最大值就是我们刚刚自己添加进去的值成功解决了这个Top-K问题这样做不仅效率高还只开辟了K个元素大小的堆上图中只开辟了2个元素大小的堆就完成了10万个数据可以说非常好用 那么今天堆的应用就讲到这里分别是堆的思想演变来的堆排以及使用堆解决Top-K问题高效又不占空间堆这部分的内容就到这里后面我们就开始介绍二叉树的链式结构存储了敬请期待吧 bye~
