algorithm - 堆排序伪代码算法

堆内排序算法

n=m
for k:= m div 2 down to 0
    downheap(k);
repeat
    t:=a[0]
    a[0]:=a[n-1]
    a[n-1]:=t
    n—
    downheap(0);
until n <= 0

有人能给我解释一下排队的事吗

    n=m
    for k:= m div 2 down to 0
        downheap(k);

我认为这是堆构建过程，但什么是for k:= m div 2 down to 0
n也是项的数目，所以在数组表示中，最后一个元素存储在[n-1]中？
但为什么n>=0我们不能在n>0结束吗？因为第一个元素被自动排序了？

最佳答案

n=m
for k:= m div 2 down to 0
    downheap(k);

在二进制堆中，一半的节点没有子节点。所以你可以从中间点开始，筛选出一个堆你在这里做的是从下往上堆。考虑以下五项：

[5, 3, 2, 4, 1]

或者，作为一棵树：

     5
  3     2
4   1

长度是5，所以我们想从索引2开始（假设一个基于1的堆数组）。然后，downheap将查看标记为3的节点，并将其与最小的子节点进行比较。由于1小于3，我们交换项目：

     5
  1     2
4   3

既然我们达到了叶子的水平，我们就完成了这个项目转到第一个项目，5。它小于1，因此我们交换项目：

     1
  5     2
4   3

但是项目5仍然大于其子项，因此我们进行另一个交换：

     1
  3     2
4   5

我们结束了。你有一个有效的堆。
手工（用铅笔和纸）做这件事对建立一个更大的堆很有指导意义——比如说10个项目。这将使你对算法的工作原理有很好的了解。
为了以这种方式构建堆，数组索引从0或1开始并不重要。如果数组是基于0的，那么您最终会对downheap进行一次额外的调用，但这不会起任何作用，因为您尝试向下移动的节点已经是一个叶节点。所以它稍微有点低效（一个额外的呼叫downheap），但并不有害。
但是，重要的是，如果根节点位于索引1处，则使用n > 0而不是n >= 0停止循环。在后一种情况下，您很可能最终会向堆中添加一个伪值，并删除一个应该存在的项。