关于Min Max Heap DeleteMin的时间复杂度

Question

在以下关于min-max heap delete-min过程的代码片段的for循环中，为什么last=(*n)/2？那是因为在最坏的情况下，x 必须插入到...的孙子的孙子中，例如：树高 5：最小最大最小最大最小，floor(5/2)=2，因为在最坏的情况下，第一级之后只有两分钟。现在又一个：height 4: min max min max, floor(4/2)=2, 这次不行了。我想也许 last=(*n) 会起作用，甚至 for(i=1;;) 也会起作用，因为它只是检查不会发生的事情？题目原因是IIRC the time complexity of min-max heap deletion is
O(log n) 但是 (*n)/2 让它看起来，嗯，像 O(n).

element delete_min(element heap[], int *n) {

    int i, last, k, parent;
    element temp, x;

    if (!(*n)) {
        // checking
    }

    heap[0] = heap[1];

    x = heap[(*n)--];

    for (i=1, last=(*n)/2; i<=last; ) {
        k = min_child_grandchild(i, *n);
        if (x.key <= heap[k].key)
            break;

        heap[i] = heap[k];
        if (k <= 2*i+1) {
            i = k;
            break;
        }

        parent = k/2;
        if (x.key > heap[parent].key)
            SWAP(heap[parent], x, temp);
        i = k;
    } // end for

    heap[i] = x;

    return heap[0];
}

来源：

Answer 1

如果在大小范围 n 上线性迭代，则循环执行 O(n) 次。线性在这里意味着你有一些循环索引，每次通过添加一个常量来修改循环索引，通常但不一定是 1:

for(i = 0; i < n; i += c) { /* Loop executes O(n) times */ }

但这不是这里发生的事情。 i 没有按常量递增。它被设置为 k，其中 k 是 i 的某些 child 或 grandchild 的索引。 i中索引最小的child在索引2i处；索引最小的 grandchild 位于索引 4i。（这些公式适用于基于 1 的索引，这在算法描述中很常见。）

所以循环更像这样（其中常量 c 通常为 4 但绝不会小于 2）：

for(i = 0; i < n; i *= c) { /* Loop executes O(log n) times */ }

关于Min Max Heap DeleteMin的时间复杂度

About the time complexity of Min Max Heap DeleteMin

algorithm

heap

binary-heap