c - 在将其转换为排序数组时找到堆化数组，交换总数是最大可能的

Question

受此启发post ，我用谷歌搜索了堆排序的最坏情况并找到了this question在 cs.stackexchange.com 上，但唯一的答案并没有真正回答问题，所以我决定自己把它挖出来。经过数小时的推理和编码，我已经解决了。我认为这个问题更适合放在 SO 中，所以我把它贴在这里。
问题是找到一个包含从 1 到 n 的不同数字的堆化数组，使得在将其转换为排序数组时，所有筛选操作中的交换总数是最大可能的。

Answer 1

当然有一种蛮力算法可以计算所有可能的堆化数组并计算每个数组的交换次数，我这样做是为了验证下面解决方案的结果。

---

• 让我们从 N=1 开始:1

• N=2:显然是 [2, 1]

• N=3: [3, x, 1].
  由于每次筛选调用最多会产生一些交换等于“高度(等于⌊log(n)⌋”(来自堆的底部)进行筛选调用的节点，所以我们将 1 放在数组的末尾。显然，x=2。

• N=4: [4, x, y, 1]
  在第一次 extract-max 之后，我们需要 heapify [1, x, y]。如果我们筛选到 N=3, [3, 2, 1] 的情况，因为这个筛选操作产生最多的交换，它等于“高度”，加上 N=3 时的最大交换次数，所以这是N=4时最大交换次数的场景。 因此，我们执行 "siftDown" version of heapify向后 到 [3, 2, 1]:将 1 与其父对象交换，直到 1 成为根。所以 x=2, y=3

• N = n: [n,a,b,c,...,x,1]
  所以，通过归纳法，当 N=n 时我们做同样的事情:首先extract-max，当 N=n-1。所以我们反过来做，得到我们得到的。

下面是输入N时输出满足要求的heapified数组的代码:

#include<stdio.h>

const int MAXN = 50001;

int  heap[MAXN];

int main()
{
    int n;
    int len,i,j;
    while(scanf("%d",&n)!=EOF)
    {
        heap[1]=1;
        len=1;
        for(i=2;i<=n;i++)
        {
            j=len;
            while(j>1)
            {
                heap[j]=heap[j/2];
                j/=2;
            }
            heap[1]=i;
            heap[++len]=1;
        }
        for(i=1;i<=n;i++)
        {
            if(i!=1) printf(" ");
            printf("%d",heap[i]);
        }
        printf("\n");
    }
    return 0;
}