索赔要求二进制堆的维基百科页面插入是 O(logn）在最坏的情况下，但平均 O(1)：
所需的操作数量仅取决于新元素必须上升到满足堆性质的层数，因此插入操作的最坏情况时间复杂度为 O(logn），但平均情况复杂度为 O(1)。
The 链接页面试图证明这一点如下：
然而，平均而言，新插入的元素不会在树上移动很远。特别是，假设密钥均匀分布，它有一半的机会大于其父级；考虑到它比其父母大，它有二分之一的机会比其祖父母大；鉴于它大于其父母，它有一半的机会大于其曾祖父母，依此类推[...]，因此在平均情况下插入需要恒定的时间
但这肯定是无稽之谈吧？在我看来，如果树是随机排序的，那么新元素有 50/50 的机会大于其父元素；但粗略地说，由于大元素沉入底部，随着堆的增长，这种可能性远小于 50/50。
是对的吗？
几个月来维基百科上都是这样……
对于平均堆插入时间为 O(1) 的说法有一个更好的参考：1991 年的论文“重复插入建堆的平均案例分析”由 Hayward 和 McDiarmid 撰写。（本文链接在当前维基百科文章的参考文献 4 中。）该论文又引用了 Porter 和 Simon 于 1975 年发表的论文，“随机插入优先级队列结构”它处理对堆的单次插入，并证明平均情况是 O(1)。
直观上，这个论点很简单。堆的一半是叶子，而且叶子往往更大。如果我们暂时假设叶子是堆中最大的元素（而不是趋向于变得更大），那么我们可以说新元素是叶子的概率 - 即它位于上半部分值的范围——正好是 0.5。如果新元素不是堆的叶子（概率也是 0.5），我们可以用原始堆中仅由非叶子节点组成的截断堆重复该过程，因此新元素位于第二个的概率 -最低水平将是剩余水平的一半：0.25。因此，它处于第三级的概率为 0.125，依此类推。那么我们需要搜索的预期级别数将是 1*0.5 + 2*0.25 + 3*0.125...，即 2。
当然，随机新元素大于随机二级父元素的概率实际上并不是 0.5；实际上是少了一点。但是，只要它受常数限制，计算幂级数的总和expected比较次数仍受常数限制。事实证明，该常数约为 2.6。
另请参阅这个有用的答案在讨论堆的复杂性并将其与 BST 进行对比的同时，给出了堆中恒定平均插入时间的详细图形分析。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
