heapifyUp（）方法的时间复杂度是多少？

Question

我已经看到了一些使用heapifyUp（）和heapifyDown（）方法的堆的实现。使用heapifyDown（无法我们实施heapifyUp（））为：

for(int i = heap_size/2; i >= 0; i--) 
    heapifyDown(i); 

我beleive上面的代码片断的时间复杂度是O（n）（根据Cormen）。

现在heapifyUp（）实现如下：

while(i!=0 && arr[parent(i)]>arr[i]) 
{ 
     swap(arr[i],arr[parent(i)]); 
     i = parent(i); 
} 

现在，如果我没看错的上述实施timeplexity是O（LOGN）

现在，因为O（LOGN）是更好比O（n）heapifyUp（）方法肯定做得更好。那么为什么Cormen使用自下而上的heapify（方法1）来构建堆？

请纠正我，如果我错了，哪个实施更好？

Answer 1

首先，你的两个代码片断正在做两件完全不同的事情。执行heapifyDown()的代码正在将整个阵列重新整理为堆。它移动了数组中的一半元素，整个过程的时间复杂度仅为O（n）。

您发布的代码heapifyUp()正在向堆中移动一个元素。它的时间复杂度是O（log n）。如果您要使用该方法从数组中构建堆，则总时间复杂度将为O（n log n）。

heapifyUp()和heapifyDown()用于两个不同的事情，每个用途都有一个原因。

heapifyUp()在将项插入堆时被调用。插入物品时，将其放在堆的末尾，然后通过堆过滤。最糟糕的情况是O（log n）。平均情况大不相同。平均而言，该项目不需要移动一半，因为它属于最后一行。四分之一的时间只需要升高一层。八分之一的时间只需移动两个级别，等等。

heapifyDown()用于删除最小元素。我们将最后一个项从堆移到根，然后将它在堆中移到适当的位置。从顶部向下移动时，heapifyDown（）的最坏情况是O（log n）。平均情况也是O（log n）。

您发布的循环是第二，特殊的，使用的heapifyDown()：

for(int i = heap_size/2; i >= 0; i--) 
    heapifyDown(i); 

这是O（n），因为它采取堆结构的优势。

首先，请注意，它只移动了一半的物品。其次，并非每件产品都从顶部一直移动。例如，如果我们有一堆127个物品（这将是一个7层的完整堆），那么64个物品从未被检查过，因为它们已经处于底层。物品中的32个只能移动一个地方。的物品16移动至多2个水平等你最终：使用所述循环创建堆时

64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps 

最多120个互换。

您可能使用heapifyDown()插入一个新的项目进堆的时候，但是这将是比使用heapifyUp()慢，因为平均插入必须每个项目比，如果它是从底部插入进一步移动。