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) 因此，向下调整算法的效率是远大于向上调整算法的！
，使用的是他的逻辑结构，也就是二叉树； 2.堆向上调整 这个主要是我们的建堆的过程，就是我们进行建堆的时候，这个数据从我们的叶子结点开始需要进行这个向上调整的过程； 我们从上面的这个建堆的过程是可以看到的...，这个时候发现我们插入数据之后，这个最后的解构就是一个大根堆（如图所示）； 3.堆向下调整 这个向下调整是如何引出来的，就是我们的这个数据进行插入之后，这个时候我们的大堆的结构就形成了，这个时候我们的这个父亲节点肯定就是最大的这个元素...因此这个时候我们的处理就是让这个元素向下进行比较，不断的向下调整-----------这个就是我们的向下调整的这个出现的场景； 下面的这个就是我们进行pop操作的时候，我们需要交换之后size–就可以了...，然后我们对于这个时候的0下标的位置的元素向下调整； 这个时候我们的方法就是需要找到这个时候的两个儿子里面的最大的那个元素：也就是和我们的这个父亲节点相邻的两个孩子，找到他们里面的较大的一个，如果我们比这两个里面的较大的一个小...，因此我们的这个3就需要和我们的17进行比较，这个时候发现是不满足我们的这个大根堆的定义的，因此这个就需要向下调整： child的值赋值给我们的parent,这个时候新的child就是我们这个时候的parent
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个元素依次与堆顶元素进行比较, 如果大于堆顶元素, 则替换堆顶元素, 并且向下调整堆
Because小堆的堆顶是堆里面的最小值，出堆时向下调整又变成了小堆，此时堆顶是剩下元素里面的最小值，就这样不断取堆顶（最小值）实现了升序操作。...【细致计算】 3.向下调整算法建堆 不仅仅可以向上调整算法建堆，还可以向下调整算法建堆。...两种方法 --> 向上调整算法建堆 / 向下调整算法建堆 建大堆还是建小堆取决于你想排升序还是排降序，自行选择 建大堆 --> 升序 建小堆 --> 降序 二、TOP-K问题 TOP-K问题...时间复杂度为：我们采用向下调整算法建堆，时间复杂度为O(K)，之后将N-K个数据进行向下调整，时间复杂度为(N-K)log(K) ，加在一起将小影响的忽略就是O(N) 。...(2); } //将数据存入堆里面 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //建堆，通过向下调整算法建一个小堆
然后将除去最后的最大节点剩下的节点看成一颗二叉树（此时这个二叉树除了根节点，其左右子树都是大堆）那么我们就可以利用堆向下调整法将根节点往下调整建成大堆； 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问题，由于堆总是一棵完全二叉树，用数组来进行存储会非常方便，也有有益于接下来对于普通二叉树的理解。
，所以我们要建小堆，堆顶的数据就是最小的我们把它和最后一个元素交换然后删除（伪删除），然后向下调整，选出第二小的然后在和倒数第二个元素进行交换，在向下调整，直至排序完毕，从后往前排不就是降序了，时间复杂度为...= n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } } 这里还有一种更优的算法叫向下调整建堆算法...，需确保子树是堆，我们从倒数第一个非叶子节点进行向下调整，倒着往回调，这种向下调整算法时间复杂为O(N) void TestHeap2() { int a[] = { 4,2,8,1,5,6,9,7...(时间复杂度本来看的 就是近似值，多几个结点不影响最终结果)： 由此可见我们向下调整建堆算法时间为O(N) 我们再来看一下向上调整算法的时间复杂度，证明如下： 由此可见我们向上调整建堆算法时间为O(N*...堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。 向上调整算法和向下调整算法是堆数据结构和堆排序中的关键算法。它们通过比较和交换元素的位置来维持堆的性质，并确保堆始终满足其定义。
下面各个函数是以建小堆为目的实现的。 2.1堆向下调整算法 能运用向下调整算法AdjustDown()的前提是，除根节点以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...同理，能运用向上调整算法AdjustUp()的前提是，除要插入节点的位置（即下标为size）以外其余都以满足小堆的条件（即父亲节点小于各个孩子节点）。...与向下调整算法不同的是，AdustUp()只需要两个参数，一个为a表示需要调整的数组（堆），另一个为child表示所需调整节点的下标（即数组最后一个元素）。...与向下调整算法不同的是，向上调整不需要比较两个孩子的大小，因为其余节点已满足父亲节点大于孩子节点。...4，5，6，7，8] 解： 首尾互换，堆顶向下调整 下列关于向下调整算法的说法正确的是（B） A.构建堆的时候要对每个结点都执行一次 B.删除操作时要执行一次 C.插入操作时要执行一次 D
笔者近日实现了最小堆类及其派生的优先级队列，特将代码奉上，不足之处还请指出！ ...后来各种补上this->才完事，在CSDN（笔者的帖子地址☞ http://bbs.csdn.net/topics/391806995）上提问后才知道是模板参数依赖，笔者表示涨姿势了。。
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个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素 ，然后再将交换进去后的元素向下调整
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
建堆 建堆的过程有两种，一是向上调整法，另一种是向下调整法，但是更快的是向下调整法，因为堆是类似于一个三角形，越往下，元素就越多，向上调整，堆顶的结点一定不用在向上调整了，因为堆顶上面没有父节点了，而向下调整法是叶子结点不用在向下调整了...那么，肯定是向下调整法的时间复杂度比较低。...例：降序，图像理解 然后让5之前的数进行向下调整，从而不打乱小堆的结构。 再让堆顶的10与30交换 最后以此类推。...对于Top-K问题，能想到的最简单直接的方式就是排序O(N*logN)，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。...小堆方法 用数组中前K个数建立一个小堆，小堆的容量也就是我们需要的数量，这时就需要交换小堆里面的数了，因为堆顶的数是最小的，所以我们遍历K后面的数，也就是N-K个数，如果比堆顶的大就和堆顶交换，之后再进行向下调整
将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。 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，堆为空，反之则非空。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
腾讯会议
云直播
对象存储
