如何建立堆树? [英] how to build heap tree?

问题描述

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

I understand the algorithm of building heap tree (max or min) but i don't understand the code of it:

首先:此循环如何建立最大堆?为什么我们以n/2-1开头i?

First: How does this loop build a max heap?, why we started the i with n/2-1 ?

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

这是Heapify函数:

and this is the Heapify function:

其次:我们如何假定最大的是"i"?

Secondly: how did we assume that largest is "i" ?

第三:为什么我们在最后一行再次进行堆化?

Third: why we heapify again in the last line?

// 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

The code and the algorithm i got,is from GeeksForGeeks

推荐答案

让我们以构建max堆的非常简单的示例来完成此操作，我认为它将回答您的问题.想象一下，您有一个数组 [3，1，6，4，4，7，9] .对应于此二叉树:

Let's do this with a very simple example of building a max heap, which I think will answer your questions. Imagine you have the array [3, 1, 6, 4, 7, 9]. That corresponds to this binary tree:

     3
  1     6
4   7 9

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

The idea of the algorithm is to push things down the heap to their proper place. Your first question is why we start at i = n//2. The simple answer is that any node at position greater than i//2 is a leaf; it has no children and therefore cannot be pushed down. Actually, we can start at (n-1)//2, because if n is even then the first non-leaf node is there, and for an odd number, (n-1)//2 == n/2.

因此，在这种情况下，为 i = 2 .下一个问题是为什么我们假设索引 i 处的元素最大.我们没有.我们从此开始，因为我们必须找到三个项中的最大项( i 中的项及其两个子项).所以我们只是默认为 i .您可以根据需要将 largest 设置为左孩子，然后进行比较.但是没有特别的理由这样做.您必须从 something 开始，索引为 i 的项目是最简单的.

So in this case, i=2. Your next question is why we assume that the element at index i is the largest. We don't. We start with that, because we have to find the largest of the three items (the item at i and its two children). So we just default to i. You could, if you want, set largest to the left child, and then do the comparisons. But there's no particular reason to do it that way. You have to start with something, and the item at index i is the easiest.

在这种情况下，索引为 i 的项为6.我们检查了该项的子项，发现9大，因此我们进行交换.结果是:

In this case, the item at index i is 6. We examine the item's children and find that 9 is larger, so we swap. The result is:

     3
  1     9
4   7 6

我们递减 i ，给我们 i = 1 .查看那里的项目及其子项，我们看到7是最大的项目，因此我们交换了两个项目，得出:

We decrement i, giving us i=1. Looking at the item there and its children, we see that 7 is the largest, so we swap the two items, giving:

     3
  7     9
4   1 6

现在我们已经扎根.9是根及其子节点中最大的，因此我们交换:

And now we're at the root. 9 is the largest among the root and its children, so we swap:

     9
  7     3
4   1 6

这是您第三个问题的答案:为什么递归调用 heapify ?您必须将项目向下推到堆的最远处.在这里，3小于6，因此我们必须交换这些项以得出:

And here's the answer to your third question: why the recursive call to heapify? You have to push the item down the heap as far as it will go. Here, 3 is smaller than 6, so we have to swap those items to give:

     9
  7     6
4   1 3

这篇关于如何建立堆树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！