algorithm - 插入堆的时间复杂度

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) ，原因是你的堆总是被假定为平衡的，即除了底层之外，每个高度级别的节点集都是满的.因此，当您在底层插入一个元素并从堆中的一个级别向上交换到下一个级别时，该级别的节点数大约减半，因此您只能执行此交换 log_2(n) = O (lg n) 次在你到达根节点之前(即堆顶部只有一个节点的级别)。而且，如果您插入一个属于堆顶部的值，最初是在堆底部，那么您实际上基本上必须进行 log_2(n) 交换以使元素到达它所属的堆顶部。所以最坏情况下的交换次数是 Theta(lg n)。