algorithm - 如何构建堆树？

Question

我了解构建堆树(最大或最小)的算法，但我不了解它的代码:

首先:这个循环是如何构建最大堆的？为什么我们以 n/2-1 开始 i？

// Build heap (rearrange array) 
for (int i = n / 2 - 1; i >= 0; i--) 
    heapify(arr, n, i); 

这是 Heapify 函数:

其次:我们如何假设最大的是“i”？

第三:为什么我们在最后一行再次heapify？

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 

我得到的代码和算法，来自GeeksForGeeks

Answer 1

1)考虑堆结构

              M
       K            L
   G       H     I     J  
 A  B    C  D   E  F  

最后一层最多包含所有项目的一半 ((n+1)//2)，因此索引 n/2-1 处的项目始终是最后一级的最后一项。从该索引开始，向左遍历，我们正在对三项迷你堆进行排序，然后向上和向左遍历，我们正在对 7 项堆进行排序，依此类推。

2) 这是条件任务的简单初始化——如果我们找到更大的后代，它会替换父代

3)如果parent被替换了，它向下移动，可能比新的后代更小，所以我们必须检查(small element sinks down)