Max Heapify Algorithm

Question

我有点困惑。如果我有一个数组，我必须建立一棵树。为了比较子节点，我必须知道我的数组在这种情况下的大小N = 6，所以我必须将其除以2，得到3。这意味着我必须从索引3开始才能与父节点进行比较。如果子节点大于父节点，则必须交换它，否则不必交换。然后，我转到索引2并与父级进行比较，如果子级大于父级节点，则必须交换它。然后索引1我必须与孩子进行比较，并在需要时进行交换。所以我创建了一个Max堆。 但是知道我不明白，但是为什么我必须将A 1与A [6]交换，然后将A 1与A [5]交换。最后我没有得到最大堆，我没有得到最小堆？ Heapify是什么意思？

非常感谢我的每一个回答！

我的一项练习是通过填充数组和树表示来说明Heapsort的步​​骤

Answer 1

[堆数据结构有很多实现，但是其中一个在讨论特定的implicit binary heap。 Heap-sort是就地完成的，因此它使用此设计。二进制堆需要一个compete binary tree，因此它可以表示为在数组外部构建的隐式结构：对于从零开始的数组中的每个A[n]，

• A[0]是根；如果n != 0，则A[floor((n-1)/2)]是父级；
• 如果2n+1在数组的范围内，则A[2n+1]是左子节点，否则它是叶节点；
• 如果2n+2在数组的范围内，则A[2n+2]是正确的子级。

说一个数组，[10,14,19,21,23,31]，使用上述规则，由同态隐式表示，]]

这不是遵循最大堆不变式，因此必须为heapify，可能使用Floyd's heap construction，后者使用sift down并在O(n)中运行。现在您有了一个堆和一个没有长度的排序数组([31,23,19,21,14,10],[])（这是隐式的，因为堆不占用额外的内存，所以它只是内存中的数组。）现阶段堆的可视化，

我们弹出堆的最大元素，然后使用sift up恢复堆形状。现在，堆变小了，我们采用了最大元素并将其未移位地存储到我们的数组([23,21,19,10,14],[31])，

中

重复，([21,14,19,10],[23,31])，

([19,14,10],[21,23,31])，

([14,10],[19,21,23,31])，

([10],[14,19,21,23,31])，

堆的大小为1，所以一个人的最终排序数组为[10,14,19,21,23,31]。如果使用最小堆和相同的算法，则将以另一种方式对数组进行排序。

Answer 2

堆排序是两个阶段的过程。在第一阶段，将数组变成堆，其最大值在顶部A [1]处。这是第一个用红色圈起来的过渡。在此阶段之后，堆位于索引1到6的数组中，最大值位于A [1]中的索引1处。