如果相邻的两个堆满足
m
a
x
[
i
]
≤
m
i
n
[
i
+
1
]
max[i]\le min[i+1]
max[i]≤min[i+1]，那么我们可以交换两个堆的位置。我们只需要说明任何
v
v
v经过两个堆过后弹出的元素相同并且
m
a
x
[
i
]
≥
m
i
n
[
i
+
1
]
max[i]\ge min[i+1]
max[i]≥min[i+1]。后者是显然的。前者也是显然的
那么现在我们可以合并了。
考虑分析复杂度。如果满足
m
a
x
[
i
]
>
m
i
n
[
i
+
1
]
max[i]>min[i+1]
max[i]>min[i+1]那么一定会发生变化
设当前有
L
L
L对堆。重叠部分
∑
ϕ
(
i
)
=
k
\sum \phi(i)=k
∑ϕ(i)=k，那么根据鸽巢原理在期望状态下经过
2
k
L
\frac{2k}{L}
L2k轮后至少有一半
ϕ
(
i
)
\phi(i)
ϕ(i)变成
0
0
0，那么就会有一半的堆被合并掉