插入堆的时间复杂度

我试图主要理解在堆中插入新元素的大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％？

来源

2015-03-02 user1010101

是的，你是对的。但是你知道为什么插入堆O（log n），这是什么意思？ – libik 2015-03-02 21:04:53

这将有助于，如果你能解释，我可能没有正确的理解...... – user1010101 2015-03-03 00:23:36

是的，你是对的最好的情况下运行时间。对于最糟糕的运行时间，你也是对的，这是Theta（lg n），原因是你的堆总是被认为是平衡的，即每个高度水平集的节点都是满的，除了在底部水平。所以，当你在底层插入一个元素并且从一个层次切换到堆中的下一个层次时，该层级的节点数量大约减少一半，因此你只能做这个交换log_2（n）= O （lg n）次，然后再进入根节点（也就是只有一个节点的堆顶部的层次）。如果你插入一个属于堆顶部的值，最初在堆的底部，那么你确实必须做基本的log_2（n）交换来获取元素到它所在堆的顶部。所以最差情况下的互换次数是Theta（lg n）。

来源

2015-03-03 01:07:42 user2566092

你的理解是正确的。由于堆有一个完整的二叉树结构，其高度= lg n（其中n不是元素）。在最坏的情况下（插入底部的元素必须在从底部到顶部的每个级别交换到根节点以保持堆属性），每个级别需要1个交换。因此，执行此交换的最大次数为log n。因此，在堆中插入需要O（log n）时间。

来源

2015-04-12 17:45:45 user2700887

“几乎完成” – Maderas 2017-05-04 15:23:57

插入堆的时间复杂度

回答

相关问题