chi*_*ity 10 algorithm heap insert time-complexity
信中的权利要求为二进制堆Wikipedia页面是插入是O(登录Ñ)在最坏的情况下,但O(1)平均:
所需的操作数量仅取决于新元素必须上升以满足堆属性的级别数,因此插入操作的最坏情况时间复杂度为O(log n),但平均情况复杂度为O(1 ).
该链接页面试图证明这个如下:
但是,平均而言,新插入的元素不会在树上移动很远.特别是,假设密钥的均匀分布,它有一半的机会大于其父级; 鉴于它比其父母更大,它有一半的机会比祖父母更大; 因为它比它的父母大,所以它有一半的机会大于它的曾祖父母,等等[...]所以在平均情况下插入需要恒定的时间
但这肯定是胡说八道？在我看来,如果树是随机排序的,那么新元素比其父元素大50/50的可能性; 但是,从大致来说,大型元素沉到底部,随着堆的增长,机会远小于50/50.
是对的吗？
几个月来维基百科就像这样......
ric*_*ici 22
关于平均时间堆插入为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; 它实际上少了一点.但是,只要它以常数为界,计算预期比较次数的幂级数之和仍然会受到常数的限制.事实证明,常数约为2.6.
另请参阅这个有用的答案,在讨论堆的复杂性时,将它们与BST的复杂性进行对比,给出了堆中恒定平均插入时间的详细图形分析.