@Vonov 看完了,我认为这篇文章的重点为懒删除的思想,金字塔本身结构倒不是最重要的。如果把金字塔换成一个splay(或任意可维护有序列表的数据结构)和一个链表,我仍然可以用懒删除的思想达成你的O(logn)O(\log n)O(logn)插入和O(1)O(1)O(1)删除最小值。做法如下:插入时在splay上走,得到链表里的插入位置。删除最小时不实际删除,在链表上移动。如果插入比最小值更小的数,则用splay删除一个前缀。
金字塔的复杂度证明大部分为trivial,您的说明有点累赘。