我了解构建堆树(最大或最小)的算法,但我不了解它的代码:
首先:这个循环是如何构建最大堆的?为什么我们以 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
最佳答案
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)
关于algorithm - 如何构建堆树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52600839/