algorithm - 堆插入的 O(1) 平均情况复杂度的论证

Question

关于 Wikipedia page for binary heaps 的声明是插入在最坏情况下是 O(log n)，但平均 O(1):

The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n) but an average-case complexity of O(1).

linked page试图证明这一点如下:

However, on average, the newly inserted element does not travel very far up the tree. In particular, assuming a uniform distribution of keys, it has a one-half chance of being greater than its parent; it has a one-half chance of being greater than its grandparent given that it is greater than its parent; it has a one-half chance of being greater than its great-grandparent given that it is greater than its parent, and so on [...] so that in the average case insertion takes constant time

不过，这肯定是胡说八道？在我看来，如果树是随机排序的，那么新元素大于其父元素的可能性为 50/50；但是，粗略地说，由于大元素会沉到底部，因此随着堆的增长，这种可能性远小于 50/50。

是这样吗？

在维基百科上已经有好几个月了......

Answer 1

对于平均堆插入时间为 O(1) 的说法，有更好的引用资料:Hayward 和 McDiarmid 于 1991 年发表的论文“Average Case Analysis of Heap Building by Repeated Insertion”。 (本文链接到维基百科文章的当前引用文献 4。)该论文又引用了 Porter & Simon 1975 年的一篇论文“Random insertion into a priority queue structure”，该论文处理堆中的单次插入，并证明平均情况是 O(1)。

直觉上，论点很简单。堆的一半是叶子，叶子往往更大。如果我们暂时假设叶子是堆中最大的元素(而不是趋向于变大)，那么我们可以说新元素成为叶子的概率——即它位于上半部分值范围的 - 正好是 0.5。如果新元素不是堆的叶子(也是0.5的概率)，我们可以用原始堆中仅由非叶子节点组成的截断堆重复这个过程，所以新元素在第二个的概率-最低水平将是剩余水平的一半:0.25。因此，它处于第三级的概率为 0.125，依此类推。那么我们必须搜索的预期级别数将为 1*0.5 + 2*0.25 + 3*0.125...，即 2。

当然，随机新元素大于随机二级父元素的概率并不是真的0.5；实际上少了一点。但是，只要它受常数限制，计算预期 比较次数的幂级数之和仍将受常数限制。事实证明，该常数约为 2.6。

另见 this useful answer在讨论堆的复杂性并将它们与 BST 的复杂性进行对比时，给出了对堆中恒定平均插入时间的详细图形分析。