k个元素插入到top_k函数的数组里，然后进行一次向下调整算法，将其调整为大堆，然后再用剩下的n-k个元素与堆顶元素进行比较，如果比他大进替换进堆，然后进行向下调整 void top_k(int* a,...[123] = 100000 + 3; a[456] = 100000 + 4; a[789] = 100000 + 5; int k = 5; top_k(a, 1000, k); } 向上调整算法和向下调整算法的时间复杂度...： 最坏情况下，最后一层的节点需要向上移动h-1次，依次类推，就得到总次数的表达式，然后再用错位相减法和n和h的关系就能求出时间复杂度f（n）了 在向下调整算法中： 最坏情况下，倒数第二层节点向下只移动一次...，第一层最多移动h-1次 总结下来我们就会发现，向上调整算法中是多节点乘多层数的关系，而向下调整算法则是多节点乘少层数的关系，我们进行比较就会发现其实向下调整算法的效率更高，所以在平常的排序和建堆中我们...最常用的还是向下调整算法 向上调整算法的时间复杂度为： n*log(n) 向下调整算法的时间复杂度为： log(n) 因此，向下调整算法的效率是远大于向上调整算法的！
然后将除去最后的最大节点剩下的节点看成一颗二叉树（此时这个二叉树除了根节点，其左右子树都是大堆）那么我们就可以利用堆向下调整法将根节点往下调整建成大堆； 4....图解如下： 以int a[] = {4,7,8,5,6,2,1,9}为例 1.建堆 这里利用堆向下调整算法实现： // 堆排序——建大堆 void AdjustDwon(int* a, int...没错关键在于堆向下调整算法实现的前提必须是左右子树都为堆，如果升序建了小堆，那么最开始的数就是最小的值不需要换，我们似乎可以将剩余的数再调整为一个小堆即可，但是我们用什么来调整呢？...堆向下调整算法实现吗？那你又是怎么知道剩下的数除了根节点左右子树还是一个堆呢？我们是没办法保证左右子树还是堆的，所以不能利用堆向下调整算法来实现； 而如果一开始调整为大堆就不一样了。...我们就可以将根节点也就是最大的数与最后一个数交换，再将出去交换后的前n-1个数向下调整为大堆，因为此时左右子树没有变化还是原来大堆的左右子树依旧是一个堆，可以利用向下调整算法实现，这也就是为什么升序要用大堆
小堆中某个节点的值总是不小于其父节点的值 堆总是一棵完全二叉树 三、堆的实现 堆分为大堆或小堆，无论是向上或向下调整算法，会根据大小堆的需求去修改部分的代码，其实就是修改大于小于号的问题。...使用向下调整算法的前提是需要左右子树必须是一个堆才能进行调正，如果左右子树不是一个堆，我们将不采取使用向下调整算法，而是采用向上调整算法。...堆向下调整算法只用于根节点不满某种条件时，使用向下调正算法进行调整，至于使用向下调整算法不能达到我们的预期，比如现在建小堆，从根节点和根左右节点调整，由于左右子树不是一个小堆，无法保证此时的根就是最小的值...除此之外删除节点也适合向下调整算法。...无论是向下调整算法还是向下调整算法，目的都是使得保持堆的性质，在判断语句中得以体现。想要更好地理解这个两个算法，搞清楚谁是需要被处理的节点，循环条件是什么？
堆排序是由堆这种数据结构所设计的一种排序算法 堆的分类： 大根堆：每个父结点的值都大于子结点 小根堆 ：每个父结点的值都小于子结点 在了解完堆之后，需要先了解建堆，建堆有向上建堆建大堆或者小堆，也有向下建堆建大堆或者小堆...建大堆还是小堆看子结点和父结点的比较关系是大于还是小于 向上调整算法 新数据插⼊到数组的尾上，再进行向上调整算法，直到满⾜堆。...⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏向下调整算法。...第h-1层，2^(h−2)个结点，需要向下移动1层 则需要移动结点总的移动步数为：每层结点个数 * 向下调整次数 向下调整算法建堆时间复杂度为：O(n) 堆排序的应用 //堆排序 void...第h层，2^(h-1)个结点，交换到根结点后，需要向 下移动h-1层 通过分析发现，堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致，此处 不再赘述。
前言 本文的学习任务：关于堆的实现以及相关的基础操作，包括向上调整算法和向下调整算法，同时利用该算法解决常见的topk问题，之后再对两种算法的时间复杂度进行分析，加深理解。...大堆还是小堆？我们需要进行调整 向上调整算法 以大堆为例子，小堆反过来就可以。...这里就要用到向下调整算法。...前面一直说向上调整算法用来建堆，向下调整算法用来删除，其实有点过于局限，Topk问题和堆排序我也采用向下调整算法来进行建堆是有原因的。...堆的核心算法是向上调整算法和向下调整算法，通过这两种算法来解决堆排序问题和TopK问题，由于堆总是一棵完全二叉树，用数组来进行存储会非常方便，也有有益于接下来对于普通二叉树的理解。
下面各个函数是以建小堆为目的实现的。 2.1堆向下调整算法 能运用向下调整算法AdjustDown()的前提是，除根节点以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...同理，能运用向上调整算法AdjustUp()的前提是，除要插入节点的位置（即下标为size）以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...与向下调整算法不同的是，AdustUp()只需要两个参数，一个为a表示需要调整的数组（堆），另一个为child表示所需调整节点的下标（即数组最后一个元素）。...与向下调整算法不同的是，向上调整不需要比较两个孩子的大小，因为其余节点已满足父亲节点大于孩子节点。...4，5，6，7，8] 解： 首尾互换，堆顶向下调整 下列关于向下调整算法的说法正确的是（B） A.构建堆的时候要对每个结点都执行一次 B.删除操作时要执行一次 C.插入操作时要执行一次 D
1.3堆的结构 二、堆的实现 2.1堆向下调整算法（父亲与孩子做比较） 我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。...向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...以下面图片为例：建小堆过程中父亲不断与较小的孩子交换 用代码来实现： void AdjustDown(HPDataType* a, int n, int parent)//n是参与向下算法的元素的个数...删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。...建堆： 升序：建大堆，降序：建小堆。 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
最大堆的插入代码 /* * 最大堆的向上调整算法(从start开始向上直到0，调整堆) * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。...二叉堆的删除代码 /* * 最大堆的向下调整算法 * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。...} /* * 最大堆的向下调整算法 * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。...= new ArrayList(); } /* * 最小堆的向下调整算法 * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，...return 0; } /* * 最小堆的向上调整算法(从start开始向上直到0，调整堆) * * 注：数组实现的堆中，第N个节点的左孩子的索引值是
建堆 建堆的过程有两种，一是向上调整法，另一种是向下调整法，但是更快的是向下调整法，因为堆是类似于一个三角形，越往下，元素就越多，向上调整，堆顶的结点一定不用在向上调整了，因为堆顶上面没有父节点了，而向下调整法是叶子结点不用在向下调整了...那么，肯定是向下调整法的时间复杂度比较低。...例：降序，图像理解 然后让5之前的数进行向下调整，从而不打乱小堆的结构。 再让堆顶的10与30交换 最后以此类推。...对于Top-K问题，能想到的最简单直接的方式就是排序O(N*logN)，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。...小堆方法 用数组中前K个数建立一个小堆，小堆的容量也就是我们需要的数量，这时就需要交换小堆里面的数了，因为堆顶的数是最小的，所以我们遍历K后面的数，也就是N-K个数，如果比堆顶的大就和堆顶交换，之后再进行向下调整
i=0; i<m_size; i++) if (data==m_heap[i]) return i; return -1; } /* * 最大堆的向下调整算法...i=0; i<m_size; i++) if (data==m_heap[i]) return i; return -1; } /* * 最大堆的向下调整算法...for(i=0; i<m_size; i++) if (data==m_heap[i]) return i; return -1; } /* * 最小堆的向下调整算法...] = m_heap[--m_size]; // 用最后元素填补 minheap_filterdown(index, m_size-1); // 从index号位置开始自上向下调整为最小堆...return 0; } /* * 最小堆的向上调整算法(从start开始向上直到0，调整堆) * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N
将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。 2.堆的性质 • 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值； • 堆总是⼀棵完全⼆叉树。...向上调整算法 • 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后 • 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可 （要求插入前必须是堆）！！！！！！...parent; parent = (child - 1)/2; } else { break; } } } 计算向上调整算法建堆时间复杂度 向上调整算法建堆时间复杂度为...：O(n ∗ log2 n) 3.3 向下调整算法 向下调整算法 • 将堆顶元素与堆中最后⼀个元素进⾏交换 • 删除堆中最后⼀个元素 • 将堆顶元素向下调整到满⾜堆特性为⽌ ！！！！！！...向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。 void adjustdown(int* a,int n, int parent) //向下调整法，！！！！！！
，这就要利用我们下面介绍的向下调整算法。...堆向下调整算法 现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...int array[] = {27,15,19,18,28,34,65,49,25,37}; ①下面介绍第一种向下调整为小堆； 前提条件——左右子树都是小堆 //堆向下调整算法（小堆） void AdjustDown...，所以要找到孩子中较小的一个进行比较； 如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。...，那么往一个堆中插入元素是没办法保证大于或小于其父节点的，所以我们插入之后需要调整这个二叉树来保证堆； 这里就要用到堆向上调整算法了；注意下面是小堆的调整 堆向上调整算法 //向上调整 void
堆的性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树 根据大根和小根我们将堆分为大堆小堆 2.2堆的实现 这里我们首先介绍堆的向下调整。...所谓向下调整就是从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...简单来说，向下调整就是将根节点和左右孩子节点进行比较若他比左右孩子中的任一数大就进行替换(小堆)，若都小就和左孩子进行替换。...删除(特指删除根节点)可以将数组最后的数将根节点覆盖，然后对根节点进行向下调整。...建堆 升序：建大堆 降序：建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...int array[] = {27,15,19,18,28,34,65,49,25,37}; 下面介绍向下调整为小堆； 前提条件——左右子树都是小堆 //堆向下调整算法（小堆） void AdjustDown...，所以要找到孩子中较小的一个进行比较； 如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。...此外堆向下调整算法还可以将一串数据调整为一个堆： 当然堆向上调整算法也可以实现，只不过它的时间复杂度没有堆向下调整算法好，所以我们选择使用堆向下调整算法构建堆 ✨堆向上调整算法 我们知道堆的父节点必须都大于或小于子节点...，大家可以依照堆的向下调整自己试试看写一下大堆的向上调整 ✨仿函数 有了堆向下调整算法来删除堆顶元素和建堆，以及堆向上调整算法尾插元素，我们就可以实现优先级队列了 但是优先级队列能否按照我们需要选择大堆还是小堆呢
前言 hello hello~ ，这里是大耳朵土土垚~ ，欢迎大家点赞关注收藏 1.建堆的方法 给你一个顺序表或数组（一串数据），通常来说建堆有两种方法一种堆向上调整算法，一种堆向下调整算法建堆也就是筛选法建堆...筛选法建堆是一种快速建堆的方法，它是在堆排序算法中使用的。这种方法的基本思想是通过不断筛选节点，如果建大堆就将大的节点向上筛选，小的节点向下筛选，小堆就反之，最终得到一个有序的堆。...NlogN logN是以2为底的 3.筛选法建堆及时间复杂度 筛选法建堆需要利用我们的向下调整算法： ✨堆向下调整算法 //堆向下调整算法 void AdjustDown(int* arr,int...小堆就建好了： 代码如下： int main() { int arr[] = { 1,8,9,5,3,2 }; //使用堆向下调整算法建堆，需要从最后一个非叶子节点开始依次往下调整 int...n ✨时间复杂度计算 由上图可知，堆向下调整法建堆的时间复杂度是N 4.结语 由上述时间复杂度的分析可知，我们最好选用筛选法也就是堆向下调整算法建堆，以上就是今天所有的内容啦~ 完结撒花~
[3，2，5，7，4，6，8] B[2，3，5，7，4，6，8] C[2，3，4，5，7，8，6] D[2，3，4，5，6，7，8] 选择题答案： 1.A 2.C 3.C 4.C 堆的实现： 堆向下调整算法...我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...exit(-1); } php->a[php->size] = x; php->size++; AjustUp(php->a, php->size - 1); } } //向下调整算法的前提条件是保证左子树右子树均为小堆...O(N) //大思路：选择排序 依次选数 从后往前排 //升序—建大堆 //降序—建小堆 //改堆排序的升序和降序只需要改变向下调整算法的大于号和小于号 //如果升序建小堆如何依次选次小的数据出来 //...//通过向下调整算法选好n-1个数 最小的数自然就在前面了 int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a,
笔者近日实现了最小堆类及其派生的优先级队列，特将代码奉上，不足之处还请指出！ ...后来各种补上this->才完事，在CSDN（笔者的帖子地址☞ http://bbs.csdn.net/topics/391806995）上提问后才知道是模板参数依赖，笔者表示涨姿势了。。
2-3删除堆顶元素-向下调整算法 2-4完整代码 3.两种方法建堆: 3-1向上调整法建堆 3-2向下调整法建堆 3-3.完整代码 3-4.两种建堆方式的时间复杂度 4.堆排序 5.TopK问题...向上调整法使用前提：树本身就是大堆或者小堆 时间复杂度：LogN 纠正上图：应该是向上调整算法，下图是向上调整法的图解实现 你是否有一个问题就是为什么在将12向上调整的时候，只用关心...小根堆就是要把小的换上去 大根堆就是要把大的换上去 因此同样顺序表插入代码，只需在调整部分稍作修改 也就是只需改一下调整部分代码的判断条件 2-3删除堆顶元素-向下调整算法 错误的顺序表式删除头...： 正确的删除堆顶元素方式：向下调整算法 前提：堆顶的把左子树和右子树都是大堆或者小堆。...向下调整算法：将要删除的堆顶元素和数组的最后一个元素先做一个交换，交换后覆盖删除数组的最后一个元素，，将堆顶元素做一次向下调整。
这里我们由于是学习堆排序，所以下面我只介绍堆的大小堆建立，向上调整算法，向下调整算法。其余堆相关知识会在另一篇文章详细介绍。...小堆原理相同，只需更改大于号和小于号。 2.1.3 向下调整算法 建立好堆之后，如何进行排序呢?这时就需要向下调整算法。首先我们要有一个共识： 排升序建大堆；排倒序建小堆。...之所以这样是因为向下调整算法的缘故，下面我们来看向下调整算法，之后解释原因。 以排升序为例 首先头元素与尾元素交换位置。 然后从头开始向下调整，如果父母节点大于孩子节点中较大的，则交换。...我们理解向下调整算法之后就可以发现 **排升序建大堆；排倒序建小堆。**是非常巧妙的， 以排升序为例，每次放在交换到首元素 的都是最小值（最大值），然后向下调整，把它放到该放在的位置上。...因为向上调整算法可以有向下调整算法来代替。
，叫做大堆，或者大根堆，或者最大堆 4.反之，则是小堆，或者小根堆，或者最小堆 5.堆的基本作用是，快速找集合中的最值 2.大/小 根堆 2.1小根堆 ?...，现在我们通过算法，把它构建成一个堆。 ...这棵二叉树调整为 大根堆 必须将 每颗子树都调整为大根堆. 3.1向下调整 思想 步骤： parent —> 根节点下标 child —> 孩子节点下标 1.从最后一棵子树进行调整. 2.每颗子树从根节点向下调整...之前我们介绍了 向下调整 这次我们说的是向上调整，与之前向上调整的思路十分相似~~ 我们来说一下 向上调整的思路 4.1向上调整 ?...我们以实际 例子说明… 1.首尾交换 2.向下调整 重复此操作直到全部有序 ? 算法演示： ? 代码实现： ? 我们看一下排序的结果： ?
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
