插入堆的时间复杂度

Question

我试图大多理解Big O和Omega在堆中插入新元素背后的原因.我知道我可以在网上找到答案,但我真的很想透彻理解,而不仅仅是在网上找到答案而只是盲目地记忆.

例如,如果我们有以下堆(以数组格式表示)

 [8,6,7,3,5,3,4,1,2] 

如果我们决定插入一个新元素"4",我们的数组现在看起来就像这样

 [8,6,7,3,5,3,4,1,2,4] 

它将被放置在索引9中,因为这是第0个基于索引的数组,其父级将是索引4,即元素5.在这种情况下,我们不需要做任何事情,因为4 <5并且它不违反二进制堆属性.最好的情况是OMEGA(1).

但是,如果我们插入的新元素是100,那么我们必须调用运行时间为O(log n)的max-heapify函数,因此在最坏的情况下,在堆中插入一个新元素需要O(log n).

如果我错了,有人可以纠正我,因为我不确定我的理解或推理是否是100%？

Answer 1

是的,你对最好的运行时间是正确的.对于最坏情况的运行时间,你也是正确的,这是Theta(lg n),原因是你的堆总是被假定为BALANCED,即每个高度级别的节点集都是满的,除了底层.因此,当您在底层插入一个元素并从一个级别交换到堆中的下一个级别时,该级别的节点数量大致减少一半,因此您只能执行此交换log_2(n)= O (lg n)在您到达根节点之前的时间(即只有一个节点的堆顶部的级别).如果您插入一个属于堆顶部的值,最初位于堆的底部,那么您确实必须基本上执行log_2(n)交换以将该元素放到它所属的堆顶部.因此,最坏情况下的掉期数量是Theta(lg n).