在将其转换为排序数组时查找堆化数组,交换总数最大可能

受到这篇文章的启发,我搜索了最糟糕的heapsort案例并在cs.stackexchange.com上找到了这个问题 ,但唯一的答案并没有真正回答这个问题,所以我决定自己去挖掘它。 经过数小时的推理和编码,我已经解决了。 我认为这个问题在SO中更好,所以我在这里发布。
问题是找到包含从1到n的不同数字的堆化数组,这样当将其转换为有序数组时,所有筛选操作中的交换总数最大可能。

当然有一个powershell算法可以计算所有可能的堆化数组并计算每个数组的交换次数,我已经这样做来validation下面解决方案的结果。


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

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

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

  • N = 4:[4,x,y,1]
    在第一次提取-max之后,我们需要heapify [1,x,y]。 如果我们将它筛选到N = 3,[3,2,1]的情况下,因为这个筛选操作产生的交换次数等于“高度”,加上N = 3时的最大交换次数,所以这是当N = 4时,最大交换次数的情况。 因此,我们将“siftDown”版本的heapify向后转移到[ 3,2,1 ]:与其父项交换1,直到1为根。 所以x = 2,y = 3

  • N = n:[n,a,b,c,…,x,1]
    因此,通过归纳,我们在N = n时做同样的事情:在第一次提取-max之后,当N = n-1时,我们将[1,a,b,c,…,x]向下筛选到堆积数组。 所以我们向后做,得到我们的东西。

以下是输出堆积数组的代码,该数组在输入N时满足要求:

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