堆阵列 - 删除根

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); 
     } 

    } 

你可以看到，它需要最大的孩子，交换本身最大的，并保持沸腾下来最大的地方了。在这个实现中，如果左右相等，它将传播左子树。

大小为n的子树上的heapify（）的运行时间为O（1），以找到最大元素+子树上递归堆积的运行时间 - 每个子树的大小最多为2n/3，最差情况发生在树的底部正好满一半时。

因此可谓heapify的运行时间为：

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

由主定理，我们得到的是：

T(n) = O(lg n)