@Vonov 我还没仔细看，但是这开头是有矛盾。因为如果你建堆是$O(n)$，删除最小值是$O(1)$，那么您可以实现$O(n)$排序，这与比较排序$\Omega(n\log n)$矛盾

@Vonov 我稍微看了一下，没仔细看

建树不是O(n)的吧

感觉你那玩意就是个平衡树啊

@DPair 建议把标题改了，莫队怎么就是暴力了

@ComeIntoPower 哦，我指的是O(n)是排好序的状态。那我把它删掉好了，看来你们有些误解。

@142857cs 哦不，它能实现平衡树，但它只能维护最值并进行延迟标记，所以它跟普通平衡树的实现方式完全不一样，而且它的常数会很大，没必要。

@huanghaox1212 莫队不就是暴力吗。。。

@DPair lxl:?

@ noip

@Vonov 平衡树也可以通过和你的做法类似的方法做到O(1)删除最小值，不过可能没人关注，因为删除复杂度优于插入在多数情况下没有必要？

另外我还是认为你这个不能可持久化的，什么叫“不会破坏以前的左右关系”

你可以先想想可持久化treap怎么记录父亲（这可以做到，但是会严重增大常数，且与OI界常见的可持久化有很大的差距，我不认为你知道该怎么做）

@142857cs 说得好，十分抱歉，我大意了，这是我的严重疏忽，我以后写文章不会乱写了。关于可持久化，确实，即使它能实现性能也不在可接受范围内。它适用于解决的问题其实跟可持久化没太大关系，不管它了。

然后就是平衡树实现$O(1)$删除的问题，其实他可以做到批量删除，然后每次删除均摊$O(1)$，但这个复杂度是伪的，不是真$O(1)$，毕竟，我金字塔删除很多数后也是可以$O(1)$直接得到最小值的，而平衡树还需要$\log_2(n)$得到合法的最小值。它适用于大数据，就是因为他遍历的常数要比平衡树小不少。

你把它当成一种跟斐波那契堆一样的存在就行了，何必研究它究竟有多实用呢？

不过我在文章中也写了，其实面对一些问题性能真的还不错的。

@Vonov 你这个的优势主要在于使用双向链表，我完全可以写个带双向链表的平衡树，你这个就没有优势了