时间戳

首页 > 解决方案 > Heapsort: Build max heap 过程解释

algorithm - Heapsort: Build max heap 过程解释

问题描述

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

“maxheap”函数使用此计算来获取节点的左右子节点（在多个不同的示例/站点中使用相同）

int 左 = 2*i;
整数右 = 2*i + 1;

以上的逻辑/推理是什么？

此外，在 heapify 函数中，使用 i = N/2 -> 0 调用 maxheap fn
（例如，而不是 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);        
}

标签： algorithmheapheapsortminmax-heap

解决方案

以上的逻辑/推理是什么？

堆是一棵二叉树，并且在一个基于 1 的索引数组中，如下所示，要获取节点的左子节点i，您需要索引2*i，而右子节点则需要索引2*i + 1。

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

Binary tree:

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

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

maxheapor max_heapifyfunction 是一个过程，它获取一个数组和一个索引i作为输入以维护最大堆属性。的假设max_heapify是节点的左右子树i是最大堆，但节点i可能违反最大堆属性（它可能小于其子节点）。
这意味着如果我们调用max_heapify所有数组元素，所有节点都将保持最大堆属性，我们应该得到一个最大堆。但是，如果我们从数组的开头（树的根）开始，我们不能假设左右子树已经是最大堆，因此我们需要从结尾（树的叶子）开始并走到开头。另外叶子没有孩子，所以它们已经是最大堆了，我们不需要打电话max_heapify在他们。在具有 n 个元素的堆中，子数组[floor(n/2)+1..n]中的节点是叶子，因此我们可以从floor(n/2)to循环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]

推荐阅读