时间戳

首页 > 解决方案 > 关于Min Max Heap DeleteMin的时间复杂度

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

问题描述

在以下关于 min-max heap delete-min 过程的代码片段的 for 循环中，为什​​么last=(*n)/2？那是因为在更坏的情况下，必须将 x 插入...的孙子的孙子，例如：树高 5: min max min max min, floor(5/2)=2, 正确因为在最坏的情况下，第一级之后只有两分钟。现在又一个：height 4: min max min max, floor(4/2)=2，这次不行。我认为也许last=(*n)会起作用，甚至for(i=1;;)会起作用，因为它只是检查不会发生的事情？标题的原因是 IIRC 最小-最大堆删除的时间复杂度是，
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];
}

资源：

在此处输入图像描述

标签： algorithmheapbinary-heap

解决方案

如果在 size 范围内线性迭代n，则循环执行 O(n) 次。这里的线性意味着你有一些循环索引，每次循环都会通过添加一个常数来修改，通常但不一定是 1：

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

但这不是这里发生的事情。i没有被常数递增。它被设置为的某个子或孙的索引k在哪里。其索引最小的孩子在 index ；索引最小的孙子位于 index 。（这些公式适用于基于 1 的索引，这在算法描述中很常见。）kii2i4i

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

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

推荐阅读