最小堆上的摊销分析？

Question

如果在空的最小堆上我们做n任意插入和删除操作,(在min-heap中给定删除位置).为什么插入的摊销分析是O(1)和删除O(log n)？

a) insert O(log n), delete O(1)

b) insert O(log n), delete O(log n) 

c) insert O(1), delete O(1)

d) insert O(1), delete O(log n)

任何人都可以为我澄清一下吗？

Answer 1

根据您的问题和对评论的回应,我将假设一个二进制堆.

首先,插入的最坏情况是O(log n),删除最小项目的最坏情况是O(log n).这是从堆的树结构得出的.也就是说,对于一堆n个项目,树中有log(n)级别.

插入涉及(逻辑上)将项添加为树中最右侧的节点,然后将其"冒泡"到所需级别.如果新项目小于根,那么它必须一直冒泡到顶部 - 所有log(n)级别.因此,如果将数字10,9,8,7,6,5,4,3,2,1插入到最小堆中,则每次插入都会遇到最坏的情况.

去除最小元素涉及用最后一个项目替换最低项目(根),然后将项目"筛选"到其正确位置.同样,这可能需要log(n)操作.

那是最糟糕的情况.在平均情况有很大不同.

请记住,在二进制堆中,一半的节点是叶子 - 它们没有子节点.因此,如果您以随机顺序插入项目,则您插入的项目的一半时间将属于最低级别,并且没有"冒泡"要做.因此,插入操作的一半时间为O(1).另一半,一半那些将属于第二级的.等等.实际对插入执行log(n)操作的唯一情况是当您插入的项目小于现有根项目时.那么,很可能观察到的运行时行为是插入是O(1).实际上,如果将已排序的数组插入到最小堆中,那将是行为.也就是说,如果要按顺序插入值1,2,3,4,5,6,7,8,9,10.

从最小堆中删除最小项时,从堆中取出最后一项并从顶部向下筛选."一半时间"规则再次发挥作用,但这一次它对你不利.你从堆中取出的最后一个项目可能属于最低级别.因此,您必须将其一直向下筛选,这需要执行log(n)操作.有一半时间你会做所有的log(n)操作.剩下的一半你只需要做其中一个,等等.事实上,你必须减少的最小级别数取决于树的深度.例如,如果您的堆有三个以上的项目,那么您知道删除最小的项目至少需要一个筛选操作,因为下一个最低的项目始终位于树的第二个级别.

事实证明,在平均情况下,插入二进制堆所需的时间远远少于O(log n)时间.它可能更接近O(1).从二进制堆中删除更接近O(log n)的最坏情况.