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

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

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

---

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

• N = 2：显然是[2，1]

• N = 3：[3，x，1]。
  由于每次筛查调用最多都会产生与进行筛查调用的节点的“高度（等于⌊log（n）⌋”（从堆的底部开始））相等的交换次数，因此我们将1放置在数组的末尾，显然x =
  2。
  
  

• N = 4：[4，x，y，1]
  在首次提取最大值之后，我们需要堆[1，x，y]。如果我们将其筛选为N = 3，[3，2，1]的情况，因为此筛选 *** 作会产生最多等于“高度”的交换，加上N =
  3时的最大交换数，因此N = 4时最大交换次数的场景。 因此，我们将
  heapify的“
  siftDown”版本倒退到[
  3，2，1
  ]：与其父级交换1直到根为1。所以x = 2，y = 3
  

• N = n：[n，a，b，c，…，x，1]
  因此，通过归纳法，当N = n时，我们做同样的事情：在第一次提取最大后，我们向下过滤[1，a， b，c，…，x]到N =
  n-1时的堆积数组。所以我们向后做，得到我们所得到的。

这是输出输入您的N时满足要求的堆积数组的代码：

#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;}