堆插入的O(1)平均大小写复杂度的参数

Question

Wikipedia页面上关于二进制堆的声明是，在最坏的情况下插入是O（log n)，但平均为O(1)：

链接的页面试图如下说明：

但是，平均来说，新插入的元素在树中并不会移动很远。特别是，假设密钥分布均匀，它有一半的机会大于其父项；它有二分之一的机会比它的祖父母更大，因为它比它的父母更大；它有一半的机会比它的曾祖父母大，因为它比它的父母大，依此类推[...]因此在一般情况下插入需要恒定的时间

不过，这肯定是胡说八道？在我看来，如果树是随机排序的，那么新元素比其父元素大的几率是50/50；但由于粗略地说,大元素沉到底部,随着堆的增长,几率远低于50/50。

在维基百科上都是这样几个月了...

Answer 1

对于平均时间堆插入是O(1)的说法，有一个更好的参考文献：1991年Hayward&McDiarmid的论文“重复插入堆构建的平均案例分析”（average Case Analysis of heap Building by Repeative insertion）。（本文链接在目前维基百科文章的参考文献4中。）这篇论文又引用了Porter&Simon 1975年的一篇论文“Random insertion into a priority queue Structure”（随机插入到一个优先级队列结构中），该论文涉及到一个堆中的单个插入，并证明了平均情况是O(1)。

从直觉上看，这个论点很简单。堆的一半是一片叶子，叶子往往更大。如果我们暂时假设leafs是堆中最大的元素（而不是倾向于更大），那么我们可以说一个新元素是leaf--即它在值范围的上半部分中--的概率正好是0.5。如果新元素不是堆的叶子（也是概率0.5)，我们可以用仅由原始堆中的非叶子节点组成的截断的堆重复该过程，因此新元素处于第二低级别的概率将是剩余的一半：0.25。因此，它处于第三级的概率是0.125，以此类推。那么我们需要搜索的层数是1*0.5+2*0.25+3*0.125…，也就是2。

当然，随机新元素大于一个随机二级父元素的概率并不是真的0.5；其实少了一点。但是，只要它以一个常数为界，计算期望比较数的幂级数之和也将以一个常数为界。结果是常数在2.6左右。

请参阅这个有用的答案，它在讨论堆的复杂性并将其与BST的复杂性进行对比的同时，给出了堆中恒定的平均插入时间的详细图形分析。