众所周知，配对堆的均摊时间复杂度（以大根堆为例）
单次 \(merge\)(合并两堆),\(insert\)(单数插入),
\(increase\) \(key\)(增加数值),\(query\) \(max\)(查询最大值) 为 \(O(1)\)
而 \(pop\)(删除最值),\(remove\)(单数删除),\(decrease\) \(key\)(减小数值) 均摊为 \(O(log(n))\)
然而事实上仅有 \(merge\),\(insert\),\(remove\) 的操作时，
时间复杂度均摊为 \(O(1)\)，总时间为线性。
证明如下：
考虑势能分析法
定义 \(\Phi(H)\) 为堆 \(H\) 中所有根节点的相邻子节点个数 \(\times 2\)
则时时 \(\Phi(H) \geq 0\)
设 \(s(x)\) 为 \(x\) 节点相邻的子结点个数
对于 \(merge\) 与 \(insert\) 操作
假定此时我们将 \(y\) 并到 \(x\) 节点上
摊还时间为 \(O(1)+\Delta \Phi(H)=O(1)+2\times (1-s(y)) \leq O(3)\)
对于 \(pop\) 操作
设此时我们将移除 \(x\) 号节点
由于遍历了整个 \(x\) 的子节点，两两合并再整体合并， \(x\) 的子节点个数减少至少一半
摊还时间为 \(O(s(x))+\Delta \Phi(H)=O(s(x))+2\times (\frac{s[x]}{2}-s[x])=O(0)\)
由于最终势能是线性的，故而整个时间复杂度是线性的
原文：https://www.cnblogs.com/Y-B-X/p/14842545.html