插入堆的时间复杂度
Time complexity of inserting in to a heap
我主要想了解 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，那么我们将不得不调用 max-heapify 函数，该函数的时间为 运行 O(log n)，因此在最坏的情况下插入一个新元素堆占用 O(log n).
如果我错了，因为我不确定我的理解或推理是否是 100%，有人可以纠正我吗？
是的，关于最佳情况 运行 时间，您是对的。在最坏的情况下 运行 时间，你也是对的，这是 Theta(lg n) ，原因是你的堆总是被假定为平衡的，即每个高度级别的节点集都是满的，除了在底层。因此，当您在底层插入一个元素并从堆中的一个级别向上交换到下一个级别时，该级别的节点数量大约减半，因此您只能进行此交换 log_2( n) = O(lg n) 次，在您到达根节点之前（即堆顶部只有一个节点的级别）。而且，如果您插入一个属于堆顶部的值，最初是在堆底部，那么您实际上基本上必须进行 log_2(n) 交换以使元素到达堆顶部它属于.. 所以最坏情况下的交换次数是 Theta(lg n)。
您的理解是正确的。
由于堆具有完整的二叉树结构，因此其高度 = lg n（其中 n 是元素的数量）。
在最坏的情况下（底部插入的元素必须从底部到顶部直到根节点的每一层交换以维护堆 属性），每一层都需要交换 1 次。因此，执行此交换的最大次数为 log n。
因此，在堆中插入需要 O(log n) 时间。
我主要想了解 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，那么我们将不得不调用 max-heapify 函数，该函数的时间为 运行 O(log n)，因此在最坏的情况下插入一个新元素堆占用 O(log n).
如果我错了，因为我不确定我的理解或推理是否是 100%，有人可以纠正我吗？
是的，关于最佳情况 运行 时间，您是对的。在最坏的情况下 运行 时间，你也是对的，这是 Theta(lg n) ，原因是你的堆总是被假定为平衡的，即每个高度级别的节点集都是满的，除了在底层。因此，当您在底层插入一个元素并从堆中的一个级别向上交换到下一个级别时，该级别的节点数量大约减半，因此您只能进行此交换 log_2( n) = O(lg n) 次，在您到达根节点之前（即堆顶部只有一个节点的级别）。而且，如果您插入一个属于堆顶部的值，最初是在堆底部，那么您实际上基本上必须进行 log_2(n) 交换以使元素到达堆顶部它属于.. 所以最坏情况下的交换次数是 Theta(lg n)。
您的理解是正确的。 由于堆具有完整的二叉树结构，因此其高度 = lg n（其中 n 是元素的数量）。 在最坏的情况下（底部插入的元素必须从底部到顶部直到根节点的每一层交换以维护堆 属性），每一层都需要交换 1 次。因此，执行此交换的最大次数为 log n。 因此，在堆中插入需要 O(log n) 时间。