java - 堆数组 - 删除根

Question

我对堆有点困惑。我有一个整数数组作为最小堆的实现。当您从根中删除最小项时，如何计算冒泡的步骤。更重要的是，说你有

          3
      5       5
   7    8    

如果删除 3，则必须用 8 替换它并向下冒泡。然而，由于两个根子节点具有相同的值 (5) 那么它会以哪种方式向下冒泡(右或左)？这很重要，因为按顺序排列的步骤数会有所不同。

谢谢

Answer 1

我认为这真的取决于你的算法实现。移除第一项在堆排序算法中经常使用。您取出第一个元素并将最后一个元素放在它的位置。然后你在根上调用 heapify() 来决定以哪种方式向下冒泡。

void heapify(int index) {

        int l = getLeft(index);
        int r = getRight(index);
        int largest;

        if(l <= storage.length && storage[index] < storage[l]){
            largest = l;
        } else {
            largest = index;
        }

        if(r <= storage.length  && storage[largest] < storage[r]){
            largest = r;
        }

        if(largest != index){
            storage.swap(index, largest);
            heapify(largest);
        }

    }

你可以看到它取其最大的 child ，交换自己和最大的 child ，并继续在最大的 child 所在的地方冒泡。在此实现中，如果左右相等，它将遍历左子树。

heapify() 在大小为 n 的子树上的运行时间是 O(1) 找到最大的元素 + 在子树上递归 heapify 的运行时间 - 每个子树最多有大小2n/3，最坏的情况发生在树的底层正好是半满的时候。

因此heapify的运行时间可以描述为:

T(n) = T(2n/3) + O(1)

根据主定理我们得到:

T(n) = O(lg n)