堆专题里有哪些冷门但实用的知识？

堆 堆是一棵树 其中有如下性质： 父亲总>=或<=它的所有儿子 \(>=\)的叫大根堆 \(<=\)的叫小根堆 所以根节点总是堆的最小或最大值 堆中任意一颗子树也是堆 二叉堆 如不说明，堆指二叉堆 二叉堆是一颗完全二叉树 所以容易存储 可以用数组 根节点为\(1\) 左子树为\(2i\) 右子树为\(2i+1\) 所以是连续的 很容易存储 二叉堆的操作： 设堆的节点个数为\(n\) 以小根堆为例 插入元素： 可以把元素插入到堆的最后，即\(n+1\)位置 那么有可能存在这个元素<它的父亲，所以需要进行向上调整 时间复杂度\(O(log(n+1))=O(logn)\) 删除根节点: 不能直接删除，会使得堆被分开，所以要找到最后一个元素n，把它和根节点1号的权值交换，然后把n号删除（或权值清空，要看具体实现） 但是最后一个元素往往较大，与根节点交换后往往会使得根节点>子节点，所以需要进行向下调整 为什么要选用最后一个元素与根交换,是因为最后一个下面没有元素了，可以直接删掉，如果与其它不是叶节点的节点交换，那么还是删不掉，因为下面还有点 而如果和不是\(n\)的其他叶节点交换，那么删掉后就不是完全二叉树了 时间复杂度： \(O（logn-log1)=O(logn)\) 调整某个点的权值： 可以增大或减小，然后要看是大还是小根堆 如果是小根堆，那么增大权值 对它上面的节点来说是符合性质的，因为下面大，上面不变，就相当于上面小于下面 对它下面的节点来说就可能不符合性质了，因为下面不变，上面大，就可能超过下面，所以要向下调整 减小权值时要向上调整 如果是大根堆，那么增大权值要向上调整 减小权值要向下调整 设节点编号为\(k\) 向上调整就是\(O(logk)￥ 向下调整就是\)O(logn-logk)$ 向上调整： 这是关键操作。 把要调整的节点权值和它父亲比较，如果比它父亲小，就要把权值和它父亲交换 然后指针指向它父亲，再次比较/交换，直到根节点 成立原因： 设要交换的节点为\(a\)，它父亲为\(fa\) 原来\(a<fa\) 向上交换一步后，\(fa<a\) 若还需向上交换，再交换一步后,\(ffa<fa\) 原来的\(ffa\)变成了\(fa\)，而\(a\)是原来的\(fa\) 显然由之前堆的性质得原\(ffa<fa\) 所以\(fa<a\) 所以调整时没有其它节点不满足堆的性质 换言之，就是把\(a\)往上甩，上面的节点往下甩 当\(a\)到达根节点的下面时，如果还要交换，那么交换后根节点小于\(a\) 根节点就是原\(a\)，\(a\)就是原根节点 而原根节点小于任何一条分支，而原\(a\)小于原根节点，所以原\(a\)小于任何一条分支，所以向上调整成立 时间复杂度： 设要调整的节点编号为\(k\) 那么最坏调整到根节点，是一条链 所以\(O(logk)\) 向下调整： 这也是关键操作 把要调整的节点的权值和它的左右儿子中的最小值（如果有）比较，如果它比最小值大，就把它和那个最小值的节点的权值交换，然后指针指向那个最小值的节点，继续调整，直到左右儿子俱无（说明到达了叶子） 时间复杂度： 设要调整的节点编号为\(k\) 则层数为\(logk\) 总层数为\(logn\) 最坏调整到叶子 所以\(O(logn-logk）\) 正确性： 调整一次时，最小值比它小，最小值又比另一个儿子小，交换后符合了性质，然后调整第二次后，把它向下甩了一个，下面的上去了一个，但是它们本来符合堆性质，所以向下调整成立 到达叶子节点时，它无需向下调整，可以停止 建堆： 1.向上调整建堆： 从根节点开始填充（1号） 每填充一个就要向上调整（相当于插入） \(log1+log2+…+logn=nlogn\) \(O(nlogn)\) 2.向下调整建堆 从n号节点开始填充，倒着来，一直填到1号 每填充一个就要向下调整 \(nlogn-log1-log2-…-logn=O(n)\) 删除任何节点 把这个节点和最后一个节点交换，然后删除最后一个节点，但是交换前要比较这个节点和最后一个节点权值大小，若增大，就要向下调整，若减小，就要向上调整 也是\(O（logn）\)的 优先队列删除任意节点 可以用一个数组dels【】，然后每删除一个节点就要打上标记 然后当询问最小值时如果堆顶是被删除过的就出队，反复出队直到节点未被删除 实际上均摊O(logn） 删除最小值时如果堆顶被删除过的就出队，反复出队直到节点未被删除 然后删除这个节点 当询问元素个数时，维护一个变量\(x\)，表示当前队列中有多少个打着删除标记 然后用当前队列尺寸\(-x\)就是实际元素个数 当删除元素时只需要把\(x\)不断增加\(1\) 然后删除最小值时看一看有多少个打着删除标记的节点被出队 然后\(x-=\)这个个数 查询最小值时同理 均摊\(O（1）\) 二叉堆的应用对顶堆： 适用范围：动态维护第\(k\)大值（数组在变） 可以维护一个大根堆和一个小根堆 先把所有元素放进大根堆中 此时堆顶是最大值 然后大根堆不断出堆，小根堆不断入堆 当小根堆大小为\(k\)时，堆顶为第\(k\)大值（大根堆的大值进入小根堆） 然后取出堆顶，记录第\(k\)大值，然后假设把这个元素删掉 然后再更改\(k\) 那么\(k\)若增大，就把大根堆的节点再入小根堆直到\(k\)个 若\(k\)减小，则把小根堆节点入大根堆（肯定是堆顶）直到\(k\)个 这就做到了动态维护第\(k\)大值 时间复杂度： 如果先排序\(nlogn\),然后每一次询问后把第\(k\)大改成\(-1\)再排序\(nlogn\)，然后记录删掉几个了以确定下标，问\(m\)次第\(k\)大，共需\(O(nm * logn)\) 如果每一次不排序，而是改成\(-1\)然后甩到最后，那么\(O(nm+nlogn)\) 如果用对顶堆，那么 建堆\(O(n）\) 第一次是\(2k_1logn\) 第二次\(2|k_2-k_1|logn\) 第m次是\(2|k_n-k_{n-1}|logn\) 若k单调递增，则为： \(2logn(k_1+k_2-k_1+k_3-k_2+..+k_n-k_{n-1})=O(n+k_n * logn)\) 若\(k\)单调递减，则为： \(2logn(k_1+k_1-k_2+k_2-k_3+…+k_{n-1}-k_n)=O((2k_1-k_n)logn +n)\) 最大都是\(O(nlogn)\) 如果\(k\)的平均变化量为\(x\) \(xmlogn\) 若\(xlogn<n\) 则对顶堆更优 如果不是删除而是添加 那么要换一种方式 先是把第一个元素入小根堆 以后每添加一个元素就把它和小根堆堆顶比较，若它大，则把它入小根堆堆顶，否则把它入大根堆堆顶 然后如果小根堆的大小大于\(k\)，就把小根堆的元素入到大根堆，若小于，就把大根堆的元素入到小根堆 然后输出小根堆堆顶元素 时间复杂度： 第一个元素入小根堆是\(1\)次 若最终\(n\)个元素 那么每添加一个元素要\(logn\) \(k\)的平均变化量为\(x\) 每一次\(xlogn\) 总共\(O(nlogn+xnlogn)=O(xnlogn)\) 注意堆与优先队列紧密相连，可以认为堆就是优先队列，所以凡是涉及最大/小值都可以用堆考虑 堆排序： 利用堆来排序，可以先\(O(n)\)建堆 然后不断取出根节点并输出，然后删除根节点 若从大到小就用大根堆 若从小到大就用小根堆 因为根是最值 删除根后的新根一定是次最值 如此往复就排好了 建堆\(O(n)\) 排序共\(nlogn\) 总\(O（nlogn）\) 配对堆 配对堆是一种多叉树，也满足堆的性质 以小根堆为例 配对堆的存储 常常采用左儿子兄弟指针法，当然指针可以用数组代替 并不是以数组下标来访问，而是指向性的访问，\(1\)下标可能指向\(7\)下标 记录这个节点的最左儿子和它的兄弟还有权值 这样访问时可以根据父节点找出它的最左儿子，然后逐个访问儿子的兄弟，可以遍历完全 查询最小值 直接输出根节点的权值 合并 合并操作是\(O（1）\)，优于二叉堆（二叉堆合并要\(O（min(alogb,bloga)）\)，，就是一个一个把\(a\)堆的元素倒着删掉，插入到\(b\)堆） 因为它是多叉树，所以不用进行调整，可以直接合并 只需要把两堆中根节点大的那一个做儿子，较小的那一个做新根 因为小的那个本身比自己堆的所有节点小，而又比大的那个小，大的那个又比它的儿孙小，所以小的是新堆根 具体操作要先把大的的兄弟改成小的左儿子 当然如果小的没有儿子，就把小的左儿子改成大的 然后把小的左儿子改成大的 需要注意的是如果两堆又一堆为空就直接返回另一堆的根 插入元素 很简单，先给新元素开一个空间，赋值权值，儿子和兄弟为空 然后把新元素自己当成堆和旧堆合并 \(O(1)\) 比二叉堆\(O(logn)\)优 删除最小值 这个操作最复杂 就是把根节点删掉 删掉根节点后儿子们就散开了，要进行合并 那么可以从左到右两两合并，最坏有\(n-1\)个儿子\(O（n）\) 那么就不如二叉堆了 所以要优化 可以从左往右两两一组分开，最后一组可能只有一个，然后每一组先自己合并，按从左往右的顺序，然后从右往左合并每一组 第一次时先合并\(n/2\)次，再合并\(n/2-1\)次 最后还是合并了\(n-1\)次 看似没有变 但是实际上变了，因为假设最左儿子最小，那么原先的方法合并后的新根是最左儿子，它的儿子们有\(n-2\)个 而如果用新方法，那么每一组合并后都是一个根接一个儿子，从右往左合并，会发现儿子变成了\(n/2\)个 而如果再次删除的话，就会发现儿子变成了\(n/4\)个 换言之，就是把同层的数量减少了，尽量向下延伸，减少了每一次的合并次数 这样均摊复杂度是\(O(logn)\) 具体可以递归设计，把\(x，x\)的兄弟\(y，y\)的兄弟\(z\)都找出来，当然\(x\)是空或\(x\)没有兄弟说明走到头了，直接返回 然后把\(x\)/\(y\)的兄弟都置为空，接下来合并\(x\)和\(y\)，然后递归合并\(z\)及其右边的，将结果根和\(x\)和\(y\)合并后的根合并 那么删除最小值就要把根的最左儿子进行拆解与合并操作，这样会选出一个新根，这个新根来更新根节点的记录，这样虽然原根还在，但是已经失去了访问指针，等于被删除了 调整一个元素的值 减小\(x\)权值后，\(x\)以下依然是堆（包括\(x\)），但是减小了\(x\)，上面的可能就大于\(x\)了 所以要进行处理 处理方式很简单，要把\(x\)和\(x\)以下的堆提出来，和原堆合并 但是提出\(x\)时要把\(x\)和原堆分开，所以要把\(x\)的兄弟置空 但是\(x\)的左兄弟还能找到\(x\)，而\(x\)却无法访问\(x\)的左兄弟，无法置空 所以需要增加一个变量\(fa\) \(fa\)在\(x\)的左兄弟不为空的时候代表x的左兄弟，在\(x\)的左兄弟为空时说明\(x\)是最左儿子，此时\(fa\)代表\(x\)的父亲 那么合并操作时要把两个根的\(fa\)和兄弟都置为空，然后合并，把大的\(fa\)改为小的，小的的儿子的话改为大的 删除最小值时要把\(x\)/\(y\)的\(fa\)置为空 减小\(x\)的值时，要断绝\(x\)左/右/上的关系 先判断\(x\)是不是最左边的兄弟 注意\(x\)如果是根的话那么直接返回根 就是判断\(x\)的\(fa\)的左儿子与\(x\)是否相等，相等的话\(x\)就是最左边的兄弟，这样只要把\(x\)的\(fa\)的儿子置为空，\(x\)的\(fa\)置 为空，\(x\)的兄弟如果有就把\(x\)的兄弟的\(fa\)置为空，\(x\)的兄弟置为空 然后\(x\)和根合并 如果\(x\)不是最左边兄弟，那么\(x\)的\(f\)a的兄弟置空，\(x\)的\(fa\)置空 \(x\)的兄弟如果有就把它的\(fa\)置空，\(x\)的兄弟置空 再合并 如果增大\(x\)的权值，那么\(x\)以上满足堆（包括\(x\)），但是\(x\)的下面可能不满足堆 所以要把\(x\)的下面提出来一个堆和根合并 可以不用\(fa\) 直接删除\(x\)的方式来操作，这样返回一个根，\(x\)的儿子置为空，这个根和堆的根合并即可 减小元素的值是\(O（1）\)的，但是均摊复杂度是\(o(logn)\)的 增大元素的值是均摊\(O(logn)\)的 左偏树 同配对堆一样，左偏树也是一种可并堆，合并两个堆复杂度较低 左偏树是一颗二叉树，但不是完全二叉树 但不是\(O(1)\) 1.dist的定义和性质 定义外节点为一个只有一个儿子或没有儿子的节点 一个外节点的\(dist=1\) 一个空节点（不存在的节点）\(dist\)为\(0\) 一个非外节点非空结点的\(dist\)为它的子树中离它最近的外节点 的距离+1（即中间路径长度+1），注意不是外节点的\(dist+1\)！ 所以，一颗根节点\(dist\)为\(x\)的二叉树（不光左偏树），前\(x\)包括\(x\)层（层数从1开始）是满二叉树 如果\(x=1\)，那么说明根节点本身是外节点，那么前1层即根是满二叉树 如果\(x>1\),那么说明根节点本身不是外节点，那么可以知道它离最近的外节点在第x层 前\(x-1\)层必须是满的，因为前\(x-1\)层如果有不满的地方，那么就会露出叶节点或1度节点，那么\(dist\)就应该小，但现在\(dist\)不是那么小，说明前\(x-1\)层是满的 第x层也必须是满的，因为如果第x层不满，那么第\(x-1\)层的节点就会有叶子或1度节点，那么\(dist\)就是\(x-1\)了 因为前\(x\)层是满的，所以至少有\(2^x -1\)个节点 因此对于一颗\(n\)个节点的二叉树，它的根节点\(dist\)至多为它的深度\(k\)，前提是前\(k\)层满的，也就是说是满二叉树 而它的深度为\(log_2⁡(n)+1\) 或\(log_2⁡(n+1)\) 这为左偏树良好的复杂度奠定了基础 2.左偏树的定义和性质 定义左偏树为一颗二叉树，且满足堆的性质，且每个节点的左儿子dist大于等于右儿子的dist 这里都以小根堆为例 左偏树的根节点是堆的最小值 对于一颗左偏树，不存在单个右儿子的节点，但存在单个左儿子的节点 因为空节点dist为0，非空结点dist>=1 单个右儿子的dist>=1，而左儿子dist=0，不符合性质 单个左儿子dist>=1,而右儿子dist=0，符合性质 左偏树一个节点的dist=它右儿子的dist+1 如果它没有右儿子 那么它是外节点，dist=1=0+1，正确 如果它有右儿子： 那么它不是外节点 它的dist=离它最近的外节点距离+1 而左儿子dist=离左儿子最近外节点距离+1 右儿子dist=离右儿子最近外节点距离+1 因为dist左>=dist右 所以dist右+1<=dist左+1 所以dist=dist右+1 左偏树的深度与dist没有绝对关系 一条向左偏的链也是左偏树，而每个节点dist=1，但是深度可以为\(O(n)\) 3.左偏树的存储 可以用父亲加左右儿子加权值+dist来存储左偏树 4.查询最小值 只要输出堆的根节点就行 5.关键操作合并两个堆 首先比较两个堆的堆顶大小，让小的做新根节点，然后把小的的右儿子和大的递归合并 合并后把递归返回的新根作为小的右儿子 然后比较小的左儿子和右儿子的\(dist\)，若左\(dist\)<右\(dist\)，则交换左右儿子 无论是否交换都要让小的根的\(dist\)=小的右儿子的\(dist+1\) 递归结束的条件是两个根节点有一个为空，此时返回另一个 时间复杂度：合并两个大小分别\(n\) \(m\)的堆\(O（logn+logm)\) 6.插入一个元素 只需要把这个元素当作一个堆与已知堆合并即可 复杂度\(O（log1+logn)=O(logn)\) 建堆： 先放一个元素作为堆 然后之后每个元素和这个堆合并 复杂度： \(O(nlogn+n)=O(nlogn)\) 那么更快的呢，可以建一个队列，先把所有元素放进去，然后取队头两个元素出队，合并，将新根入队尾 直到取队头两个元素时只剩一个元素就停止，把这个元素记录下来就是真正的根节点 类似于配对堆删除最小值的操作 先把元素两两一组合并，\(n/2\)组，一组合并\(log1+log1\)次\(=2log1\) \(n/2\)组再两个\(1\)组，合并，\(n/4\)组，一组合并\(2log2\)次 \(n/8\)组 一组\(2log4\) . . . \(n/n\)组 \(2log（n/2)\) \(sum=2(n/2 log1+n/4 log2+n/8 log4 +…+n/n log(n/2))\) \(=2(n/2 * 0 + n/4 *1 +n /8 *2 +… +n/n *log(n/2))\) 约等于\(O（kn）\)\(k\)在\(10\)左右 7.删除最小值 把根节点的左右儿子（如果有）的父亲置为空 然后把根节点指向的儿子置为空 然后合并左右儿子，将新根作为根节点 8.删除任意节点 把要删除的节点的左右儿子（如果有）的父亲置为空 把原来节点的左右儿子置为空，同时记录左右儿子 然后合并左右儿子，返回新根 用新根代替原来节点的位置，即 先判断原来节点是它父亲的左还是右儿子 然后把它父亲的左/右儿子改成新根 新根的父亲改为原来节点的父亲 原来节点父亲置为空 因为下面的值大，删除源节点后仍是堆 但是\(dist\)可能改变 所以要循环调整父亲的\(dist\) 先找当前节点的父亲，然后看自己是左/右儿子 然后如果自己是左儿子，且\(dis\)t<右儿子的\(dist\)，那么交换左右儿子 如果自己是右儿子，且\(dist\)>左儿子的\(dist\)，那么交换左右儿子 然后如果父亲的\(dist\)=右儿子\(dist+1\)，直接终止循环 否则，更新父亲\(dist\)，然后把当前节点改成自己父亲 当当前节点为空时，终止循环 配对堆删除任意节点更为简单 就是执行删除最小值操作，但是不是根节点，而是待删除的节点 然后处理好原来节点的一些关系 原来节点有真父亲 最左儿子 右兄弟 前驱结点 如果不记录真父亲的话就不需要修改真父亲 先判断是不是最左节点，就是前驱的左儿子是否等于自己，若等于，则是，否则不是 若是，就应该把前驱的左儿子改成新根， 若不是，就把前驱的后继改成新根 然后如果原来节点有兄弟，就把兄弟的前驱改成新节点，然后把新节点的兄弟改成原来节点的兄弟，原来节点的兄弟=空 原来节点最左儿子=空 新节点的真父亲=原来节点真父亲 原来节点真父亲=空 新根的前驱改成原来节点前驱 原来节点前驱=空 斜堆与随机合并 从左偏树引出了斜堆 斜堆 就是普通的堆 是二叉树 但是是任意二叉树 以小根堆为例 但是支持合并 合并时把小的根节点作为新根，然后小的的右儿子和大的根递归合并，新的根作为小的的右儿子 最后返回新根 当一个堆为空时，返回另一个堆的根 这样会出现一个问题，就是一些右偏链的合并时，根节点的左儿子一直不变，而右儿子一直和别的合并，而右儿子里的节点也是如此，所以会导致最坏复杂度\(O（n+m）\) 所以可以在递归后返回前插入一步，把左儿子和右儿子交换 这样的话每一次递归时都会这样操作 如果再合并链，那么第一次右儿子和一个堆合并，第二次左儿子和另一个堆合并，第三次右儿子再和另一个堆合并，避免了一个儿子下面放太多节点，同时递归交换更能减小复杂度（让链空出的节点参与合并） 这样复杂度降到了均摊\(O（logn+logm)\) 随机合并是： 合并是还是先找根节点小的作为新根，然后随机决定用小的的左儿子还是右儿子和大的合并 返回新根 当有一个堆为空时，返回另一个堆的根节点 配对堆/左偏树用并查集找到节点所在根 对于左偏树来说，深度最大\(O(n)\) 所以在寻找节点的根时不能递归寻找父亲，会超时 而应该借助并查集 一般来说，题目都是从单个节点开始合并，所以可以另开一个数组，记录这个节点所指向的根 这样当合并\(x\)和\(y\)的时候直接用\(x\)的根递归到头和\(y\)的根递归到头合并，合并后把\(x/y/x\)的根/\(y\)的根 的根数组置为新根 当删除最小值时，把\(x\)的根递归到头删掉，但是数组不要清空那个根，因为那个根维护了并查集的某种关系，一旦破坏就无法查询了，所以把那个根的根数组指向新根即可，然后新根一定要指向自己，否则访问新根将会访问回旧根，引发无限循环 为什么这样可以呢？ 因为最开始都是元素之间合并，这是它们的根就是真正的根，但是当一个已有的堆和一个元素合并时，新根可能会改变，这样不可能更改每一个元素的根指向，但当改了旧根的指向后，当再访问那些元素时，它指向的是旧根，旧根又指向了新根，这样递归就能指向最终的根，同时还有路径压缩，因为当两个堆合并时，不光更改了旧根的指向，还更改了\(x\)和\(y\)的指向，进一步减小了复杂度 而删除根节点时为了不破坏某种关系，所以不能把根节点的数组删掉，而应该把它的根数组指向新根，以后反正也访问不到旧根，就利用旧根做中转节点找新根 复杂度\(O（logn）\)可能更低 如果是配对堆，还可以记录真父亲，因为配对堆高度较小，可以稳定复杂度在\(logn\)左右 而操作是合并时把大的根的真父亲改为小的根 删除最小值时每一个儿子都要把真父亲置为空 堆的几道好题: 模板堆 合并果子：每次合并最小的两个 需要注意的是两个是可以都经过合并过的再合并 中位数/running median：对顶堆 csp2020pjt2 ：配对堆+对顶堆 模板左偏树 快速排序：堆排序