如何构建堆树？

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）

Answer 2

让我们用一个非常简单的构建最大堆的例子来做这件事，我认为它会回答你的问题。假设您有数组 [3, 1, 6, 4, 7, 9]。对应这个二叉树：

     3
  1     6
4   7 9

该算法的思想是将堆中的东西推到适当的位置。您的第一个问题是为什么我们从 i = n//2 开始。简单的答案是任何位置大于 i//2 的节点都是叶子；它没有children，因此不能被推下。实际上，我们可以从 (n-1)//2 开始，因为如果 n 是偶数，那么第一个 non-leaf 节点就在那里，对于奇数，(n-1)//2 == n/2.

所以在这种情况下，i=2。您的下一个问题是为什么我们假设索引 i 处的元素是最大的。我们没有。我们从那里开始，因为我们必须找到三个项目中最大的一个（i 处的项目及其两个 children）。所以我们默认为 i。如果需要，您可以将 largest 设置为左侧 child，然后进行比较。但是没有特别的理由这样做。您必须从 something 开始，索引 i 处的项目是最简单的。

在这种情况下，索引 i 处的项目是 6。我们检查项目的 children 并发现 9 更大，因此我们交换。结果是：

     3
  1     9
4   7 6

我们递减 i，得到 i=1。查看那里的项目及其 children，我们看到 7 是最大的，所以我们交换这两个项目，给出：

     3
  7     9
4   1 6

现在我们到了根部。 9 是根和它的 children 中最大的，所以我们交换：

     9
  7     3
4   1 6

第三个问题的答案如下：为什么要递归调用 heapify？您必须将项目尽可能地向下推到堆中。在这里，3 小于 6，所以我们必须交换这些项目以得到：

     9
  7     6
4   1 3

Answer 3

一个父节点的最大子索引ci是：

ci = 2*i + 2 < size
i < (size - 2)/2
i < size/2 - 1

但您需要包括 size/2 - 1，因为一个节点可能只有一个子节点，而 i 一直到零，因为所有这些节点都是父节点。至于递归，你需要在交换后强制执行最大堆规则。

如何构建堆树？

how to build heap tree?

sorting

algorithm

heapsort