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) 因此，向下调整算法的效率是远大于向上调整算法的！
void HeapSort(int* a, int n) { //降序 //创建小堆 //向下调整创建,从最有一个非叶子节点 //时间复杂度O(N) for (int i = (n-1-1)/...int end = n-1; while (end > 0) { Swap(&a[0], &a[end]); Adjustdown(a, end, 0); end--; } } 首先来看向下调整算法建堆的时间复杂度...: 向下调整算法, 从最后一个非叶子结点开始向下调整, 也就是第h-1层, 需要向下移动一层, 第h-2层需要向下移动2层, … , 第一层则需要向下移动h-1层, 第二层的结点需要向下移动h-2层....对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。...例如: 求十万个数据中最大的前K个数, 要求只有1kb内存, 这些数据存储在磁盘中 首先先用前k个数建一个小堆, 剩下的N-K个元素依次与堆顶元素进行比较, 如果大于堆顶元素, 则替换堆顶元素, 并且向下调整堆
然后将除去最后的最大节点剩下的节点看成一颗二叉树（此时这个二叉树除了根节点，其左右子树都是大堆）那么我们就可以利用堆向下调整法将根节点往下调整建成大堆； 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层 通过分析发现，堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致，此处 不再赘述。
个数据⼀换，然后删除数组最后⼀个数据，再进⾏ 向下调整算法。...向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。...x_tz(r->arr, 0, r->size); } 计算向下调整算法建堆时间复杂度 向下调整算法建堆时间复杂度为：O(n) 堆的应用 堆排序 版本⼀：基于已有数组建堆、取堆顶元素完成排序版本...x_tz(arr, 0, i); i--; } } 向上调整算法建堆 每插入一个数值都会判断，要不要向上调整 向下调整算法建堆 通过（size-1）-1/2就能得到父亲节点，通过父亲节点往后进行向下调整...第三步：从堆顶位置开始向下调整。 第四步：i减1。 堆排序时间复杂度计算 TOP-K问题 TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。
前言 本文的学习任务：关于堆的实现以及相关的基础操作，包括向上调整算法和向下调整算法，同时利用该算法解决常见的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个节点的左孩子的索引值是
这是基于堆顶数据以下的左右子树都是堆才是才能调整的 而当我们拿到一组乱序的数据，个数为n，显然是不能从堆顶开始向下调整的 怎么办，那就换思路： 既然向下调整算法需要左右子树都为堆，那我们从最后一棵子树开始调整不就可以了吗...建好堆后，将堆顶元素与最后一个元素交换（若建小堆的则每次取的都是最小的，所以为降序） 然后将交换过去的堆顶元素进行向下调整 重复上述步骤 void HeapSort2(int* arr, int n)...，外层循环（n-1）次，内层每一次向下调整最多log2(n+1)层，时间复杂度O(nlog(n)) 总共为O(nlogn+nlogn) 所以此种堆排序为O(nlogn) 方案三 将方案二建堆算法替换为向下调整算法即可...，所以堆排序使用方案三为最佳 要排升序，建大堆->每次取最大的到最后一位 要排降序，建小堆->每次取最小的到最后一位 Top-k问题 TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都...最佳的⽅式就是⽤堆来解决，基本思路如下： ⽤数据集合中前k个元素来建堆 前k个最⼤的元素，则建⼩堆；前k个最⼩的元素，则建⼤堆 ⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素 ，然后再将交换进去后的元素向下调整
建堆 建堆的过程有两种，一是向上调整法，另一种是向下调整法，但是更快的是向下调整法，因为堆是类似于一个三角形，越往下，元素就越多，向上调整，堆顶的结点一定不用在向上调整了，因为堆顶上面没有父节点了，而向下调整法是叶子结点不用在向下调整了...那么，肯定是向下调整法的时间复杂度比较低。...例：降序，图像理解 然后让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
‧ 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。 ‧ 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。...for (int i =(n-1-1)/2 ; i >= 0; i--)//n-1为数组最后一个数据的下标，(n-1-1)/2为其父节点 { AdjustDown(arr, i, n);//向下调整算法...第h层， 2^(h-1) 个结点，需要向上移动h-1层 则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0） 由此可知， 向上调整算法建堆时间复杂度为...&arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } 计算向下调整算法建堆时间复杂度...第h-1层， 2^(h-2) 个结点，需要向下移动1层 由此可知， 向下调整算法建堆时间复杂度为：O(n) 2.6堆的判空 堆的大小为0，堆为空，反之则非空。
堆的性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树 根据大根和小根我们将堆分为大堆小堆 2.2堆的实现 这里我们首先介绍堆的向下调整。...所谓向下调整就是从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...简单来说，向下调整就是将根节点和左右孩子节点进行比较若他比左右孩子中的任一数大就进行替换(小堆)，若都小就和左孩子进行替换。...删除(特指删除根节点)可以将数组最后的数将根节点覆盖，然后对根节点进行向下调整。...建堆 升序：建大堆 降序：建小堆 2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
AdjustUp(php->arr, php->size - 1); } 向上调整算法建堆的时间复杂度为：O(N*logN) 4.2.2向下调整算法 | 堆的删除 删除堆是删除堆顶的数据，前提是...将堆顶的数据和最后一个数据交换，然后删除数组最后一个数据，为了继续满足堆需要再进行向下调整算法，结果是次小的（次大的）在堆顶。...向下调整算法建堆，从最后一个孩子的父亲开始往前依次向下调整，到堆顶时结束。...因为向上调整算法建堆的时间复杂度是：O(N*logN)，而向下调整算法建堆的时间复杂度是：O(N)，所以我们优先使用向下调整算法建堆来实现堆排序。...我们可以将大量的数据建大堆（向下调整算法优先），此时堆顶就是最大的数据，然后Topk次就能解决问题了。
笔者近日实现了最小堆类及其派生的优先级队列，特将代码奉上，不足之处还请指出！ ...后来各种补上this->才完事，在CSDN（笔者的帖子地址☞ http://bbs.csdn.net/topics/391806995）上提问后才知道是模板参数依赖，笔者表示涨姿势了。。
我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。...int array[] = {27,15,19,18,28,34,65,49,25,37}; 下面介绍向下调整为小堆； 前提条件——左右子树都是小堆 //堆向下调整算法（小堆） void AdjustDown...，所以要找到孩子中较小的一个进行比较； 如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。...此外堆向下调整算法还可以将一串数据调整为一个堆： 当然堆向上调整算法也可以实现，只不过它的时间复杂度没有堆向下调整算法好，所以我们选择使用堆向下调整算法构建堆 ✨堆向上调整算法 我们知道堆的父节点必须都大于或小于子节点...，大家可以依照堆的向下调整自己试试看写一下大堆的向上调整 ✨仿函数 有了堆向下调整算法来删除堆顶元素和建堆，以及堆向上调整算法尾插元素，我们就可以实现优先级队列了 但是优先级队列能否按照我们需要选择大堆还是小堆呢
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
