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个数向下调整为大堆，因为此时左右子树没有变化还是原来大堆的左右子树依旧是一个堆，可以利用向下调整算法实现，这也就是为什么升序要用大堆
前言 本文的学习任务：关于堆的实现以及相关的基础操作，包括向上调整算法和向下调整算法，同时利用该算法解决常见的topk问题，之后再对两种算法的时间复杂度进行分析，加深理解。...大堆还是小堆？我们需要进行调整 向上调整算法 以大堆为例子，小堆反过来就可以。...这里就要用到向下调整算法。...前面一直说向上调整算法用来建堆，向下调整算法用来删除，其实有点过于局限，Topk问题和堆排序我也采用向下调整算法来进行建堆是有原因的。...堆的核心算法是向上调整算法和向下调整算法，通过这两种算法来解决堆排序问题和TopK问题，由于堆总是一棵完全二叉树，用数组来进行存储会非常方便，也有有益于接下来对于普通二叉树的理解。
下面各个函数是以建小堆为目的实现的。 2.1堆向下调整算法 能运用向下调整算法AdjustDown()的前提是，除根节点以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...同理，能运用向上调整算法AdjustUp()的前提是，除要插入节点的位置（即下标为size）以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...与向下调整算法不同的是，AdustUp()只需要两个参数，一个为a表示需要调整的数组（堆），另一个为child表示所需调整节点的下标（即数组最后一个元素）。...与向下调整算法不同的是，向上调整不需要比较两个孩子的大小，因为其余节点已满足父亲节点大于孩子节点。...4，5，6，7，8] 解： 首尾互换，堆顶向下调整 下列关于向下调整算法的说法正确的是（B） A.构建堆的时候要对每个结点都执行一次 B.删除操作时要执行一次 C.插入操作时要执行一次 D
最大堆的插入代码 /* * 最大堆的向上调整算法(从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个节点的左孩子的索引值是
1.3堆的结构 二、堆的实现 2.1堆向下调整算法（父亲与孩子做比较） 我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。...向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...以下面图片为例：建小堆过程中父亲不断与较小的孩子交换 用代码来实现： void AdjustDown(HPDataType* a, int n, int parent)//n是参与向下算法的元素的个数...删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。...建堆： 升序：建大堆，降序：建小堆。 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
建堆 建堆的过程有两种，一是向上调整法，另一种是向下调整法，但是更快的是向下调整法，因为堆是类似于一个三角形，越往下，元素就越多，向上调整，堆顶的结点一定不用在向上调整了，因为堆顶上面没有父节点了，而向下调整法是叶子结点不用在向下调整了...那么，肯定是向下调整法的时间复杂度比较低。...例：降序，图像理解 然后让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
，这就要利用我们下面介绍的向下调整算法。...堆向下调整算法 现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...int array[] = {27,15,19,18,28,34,65,49,25,37}; ①下面介绍第一种向下调整为小堆； 前提条件——左右子树都是小堆 //堆向下调整算法（小堆） void AdjustDown...，所以要找到孩子中较小的一个进行比较； 如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。...，那么往一个堆中插入元素是没办法保证大于或小于其父节点的，所以我们插入之后需要调整这个二叉树来保证堆； 这里就要用到堆向上调整算法了；注意下面是小堆的调整 堆向上调整算法 //向上调整 void
堆的性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树 根据大根和小根我们将堆分为大堆小堆 2.2堆的实现 这里我们首先介绍堆的向下调整。...所谓向下调整就是从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...简单来说，向下调整就是将根节点和左右孩子节点进行比较若他比左右孩子中的任一数大就进行替换(小堆)，若都小就和左孩子进行替换。...删除(特指删除根节点)可以将数组最后的数将根节点覆盖，然后对根节点进行向下调整。...建堆 升序：建大堆 降序：建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
[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,
这里我们由于是学习堆排序，所以下面我只介绍堆的大小堆建立，向上调整算法，向下调整算法。其余堆相关知识会在另一篇文章详细介绍。...小堆原理相同，只需更改大于号和小于号。 2.1.3 向下调整算法 建立好堆之后，如何进行排序呢?这时就需要向下调整算法。首先我们要有一个共识： 排升序建大堆；排倒序建小堆。...之所以这样是因为向下调整算法的缘故，下面我们来看向下调整算法，之后解释原因。 以排升序为例 首先头元素与尾元素交换位置。 然后从头开始向下调整，如果父母节点大于孩子节点中较大的，则交换。...我们理解向下调整算法之后就可以发现 **排升序建大堆；排倒序建小堆。**是非常巧妙的， 以排升序为例，每次放在交换到首元素 的都是最小值（最大值），然后向下调整，把它放到该放在的位置上。...因为向上调整算法可以有向下调整算法来代替。
2-3删除堆顶元素-向下调整算法 2-4完整代码 3.两种方法建堆: 3-1向上调整法建堆 3-2向下调整法建堆 3-3.完整代码 3-4.两种建堆方式的时间复杂度 4.堆排序 5.TopK问题...向上调整法使用前提：树本身就是大堆或者小堆 时间复杂度：LogN 纠正上图：应该是向上调整算法，下图是向上调整法的图解实现 你是否有一个问题就是为什么在将12向上调整的时候，只用关心...小根堆就是要把小的换上去 大根堆就是要把大的换上去 因此同样顺序表插入代码，只需在调整部分稍作修改 也就是只需改一下调整部分代码的判断条件 2-3删除堆顶元素-向下调整算法 错误的顺序表式删除头...： 正确的删除堆顶元素方式：向下调整算法 前提：堆顶的把左子树和右子树都是大堆或者小堆。...向下调整算法：将要删除的堆顶元素和数组的最后一个元素先做一个交换，交换后覆盖删除数组的最后一个元素，，将堆顶元素做一次向下调整。
，叫做大堆，或者大根堆，或者最大堆 4.反之，则是小堆，或者小根堆，或者最小堆 5.堆的基本作用是，快速找集合中的最值 2.大/小 根堆 2.1小根堆 ?...，现在我们通过算法，把它构建成一个堆。 ...这棵二叉树调整为 大根堆 必须将 每颗子树都调整为大根堆. 3.1向下调整 思想 步骤： parent —> 根节点下标 child —> 孩子节点下标 1.从最后一棵子树进行调整. 2.每颗子树从根节点向下调整...之前我们介绍了 向下调整 这次我们说的是向上调整，与之前向上调整的思路十分相似~~ 我们来说一下 向上调整的思路 4.1向上调整 ?...我们以实际 例子说明… 1.首尾交换 2.向下调整 重复此操作直到全部有序 ? 算法演示： ? 代码实现： ? 我们看一下排序的结果： ?
堆排序可以说是排序算法中比较高效的了，既稳定又高效。...： 向下调整算法有一个前提：左右子树必须是一个堆，才能调整 这里由于是数组存储的所以堆的左右子树都是 child = parent* 2+1; 孩子节点的左节点都等于 父节点 如果堆顶数据和左右子树对比...OR 建小堆降序 // 建大堆升序 for (int i = 1; i < n; i++) { adjustup(a, i); } 3.1 如何利用向下调整建堆 利用向下调整建堆的要求是左右俩边都是堆才可以向下调整...4.1 向上调整建堆时间复杂度计算 4.2 向下调整建堆时间复杂度计算 4.3 对比结果 建堆思想 时间复杂度 向上调整建堆 O(N * logN) 向下调整建堆 O(N) 所以我们在进行堆排序的时候一定首先选取向下调整算法时间复杂度更优...假设有1000万个数据 建堆思想 排序次数 向上调整 1000W*24（约等于 2亿多） 向下调整 1000W 所以我们向下调整的算法是远远大于向上调整的这是为什么呢？
笔者近日实现了最小堆类及其派生的优先级队列，特将代码奉上，不足之处还请指出！ ...后来各种补上this->才完事，在CSDN（笔者的帖子地址☞ http://bbs.csdn.net/topics/391806995）上提问后才知道是模板参数依赖，笔者表示涨姿势了。。
) (2)向下调整算法建堆的时间复杂度 void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法 { int child = parent...，而向下调整算法的时间复杂度为 O(N) 所以使用向下调整算法建堆更好 2....堆排序时间复杂度统计 在整体过程中，主要有 向下调整算法建堆 及 排序组成 向下调整算法建堆的时间复杂度为O(N) 排序的时间复杂度为O(logN) 即堆排序的时间复杂度为O(NlogN) 4.完整代码...，所以不能进入内存中 第二种 思想 建立k个数小堆，依次遍历数据，比堆顶的数据大，就进行交换，再向下调整，最后最大的k个数就在小堆中 过程 假设共有如上的数据，n =6 ，k=3...取前k个数据建立一个小堆 再取剩余的数据依次与其比较，若比堆顶数据大，则赋值，同时进行向下调整，使堆顶为最小的数 3.完整代码 #define _CRT_SECURE_NO_WARNINGS #
父子结点 因为都是由数组表示的完全二叉树 而数组对应下标 左孩子下标 =父亲节点下标*2+1 右孩子下标 =父亲节点下标*2+2 二、向下调整算法 1.概念 向下调整算法 以小堆为例， 当满足左子树与右子树都是小堆时...实现 void justdown(int* a, int n, int root)//向下调整算法 ——建堆 小堆 { int parent = root; int child = parent...最后建堆选序的时间复杂度为O(N^2) 对比其他排序这样都没有效率 所以我们采用大堆排升序 使用大堆可以不改变二叉树本身的结构 将 堆顶与最后一个数交换 ，这样最大的数就排到最后了 再将前n-1个数再次使用向下调整算法...，找到次大的数 ，与倒数第二个数交换 直到有一个数时停止 3.代码实现 void justdown(int* a, int n, int root)//向下调整算法 ——建堆 大堆 { int...1.建堆的时间复杂度 O(N) 2.排序中运用向下调整算法 ,向下调整算法需要调整高度次h 2^h -1 =N h=log N 时间复杂度为O(logN) 不太懂高度计算的
向上调整建堆 我们先一起来分析一下向上建堆的时间复杂度: 首先,按照算法算法最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则: 使用错位相消法...再来看看向下调整建堆: 我们继续,按照算法最坏时间复杂度分析,假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则: 使用错位相消法,可得T(n)为: 化简,可得...向下调整的建堆方式的时间复杂度为 向下调整建堆是优于向上调整建堆的....k个最大的元素,新元素比堆顶要大)则用其替换堆顶,然后再向下调整,构建为新的大堆/小堆. 3.当遍历完剩下N-K个元素时,堆中剩余的k个元素就是所求的前Top-k个元素....利用这种方式选出top-k,当数据量大到可以忽略建堆以及后续调整堆部分的操作带来的时间复杂度时,我们可以近似的认为这个算法的时间复杂度为O(n).
3.1堆向下调整算法 现在我们给出一个数组，逻辑上看做一颗完全二叉树。...我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...3.4堆的插入 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。 3.5堆的删除 删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。...向下交换是指将堆顶元素与其子节点中较大的（对于最大堆）或较小的（对于最小堆）元素交换位置，然后重新调整子堆，以保持堆的性质。这个过程重复进行，直到整个堆排序完成。...通过这种向下调整的方式，可以高效地构建一个最大堆（或最小堆），为后续的堆排序等操作提供基础。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
