Heapsort: Build max heap 程序说明

Question

我正在尝试理解使用堆排序对数组进行排序的代码（参考 - https://www.sanfoundry.com/java-program-implement-heap-sort/）

"maxheap"函数就是利用这个计算得到Node的左右子节点（同一个用于多个不同的examples/sites）

int left = 2*i;
int right = 2*i + 1;

上面的 logic/reasoning 是什么？

此外，在 heapify 函数中，调用 maxheap fn with i = N/2 -> 0
（而不是 i = 0 到 N -1，例如。）关于为什么这样做有什么想法吗？

public static void heapify(int arr[])
{
     N = arr.length-1;
     for (int i = N/2; i >= 0; i--)
         maxheap(arr, i);        
}

Answer 1

What is the logic/reasoning for the above ?

堆是一棵二叉树，在一个从 1 开始的索引数组中，如下所示，要获得节点 i 的左侧 child，您需要索引 2*i 和对于右边 child 你得到索引 2*i + 1。

Array:
[1, 2, 3, 4, 5, 6, 7]

Binary tree:

         1
      /     \
   2           3
 /   \       /   \
4     5     6     7

Additionally, in the heapify function, maxheap fn is called with i = N/2 -> 0 (instead of i = 0 to N -1, for eg.) Any ideas on why this is done ?

maxheap 或 max_heapify 函数是获取数组和索引 i 作为输入以维护最大堆属性的过程。 max_heapify 的假设是节点 i 的左子树和右子树是最大堆，但节点 i 可能违反最大堆属性（它可能小于它的child仁).
这意味着如果我们在所有数组元素上调用 max_heapify，所有节点将保持最大堆属性，我们应该得到一个最大堆。但是，如果我们从数组的开头（树的根）开始，我们不能假设左右子树已经是最大堆，因此我们需要从末尾（树的叶子）开始并转到开头。此外，叶子没有 children，因此它们通常已经是最大堆，我们不需要对它们调用 max_heapify。在具有 n 个元素的堆中，子数组 [floor(n/2)+1..n] 中的节点是叶子，因此我们可以从 floor(n/2) 循环到 1 并仅在内部节点上调用 max_heapify。

对于从 0 开始的数组：

left(i):        2 * i + 1
right(i):       2 * i + 2
leaves:         [floor(n/2)..n-1]
internal nodes: [0..floor(n/2)-1]

Heapsort: Build max heap 程序说明

Heapsort: Build max heap procedure explanation

algorithm

heap

heapsort

minmax-heap