找到一个heapified阵列将其转换为一个排序后的数组时，交换的总数为最大可能

本文介绍了找到一个heapified阵列将其转换为一个排序后的数组时，交换的总数为最大可能的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

本post,我GOOGLE了堆排序的最坏情况，发现这个问题上cs.stackexchange，但唯一的答案并没有真正回答这个问题，所以我决定把它挖出来了我自己。经过推理和编码的时间，我已经解决了。我认为这个问题属于SO更好，所以我在这里发布它。 的问题是要找到包含heapified阵列不同的号码从1到n，使得它转换成一个排序后的数组时，交易所中的所有筛选操作的总数是最大可能的。

Inspired by this post, I googled the worst case of heapsort and found this question on cs.stackexchange, but the only answer didn't really answer the question, so I decided to dig it out myself. After hours of reasoning and coding, I've solved it. and I think this question belongs better in SO, so I post it up here. The problem is to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible.

推荐答案

当然，还有一个蛮力算法计算heapified阵列的所有可能和计算交往的每一个数字，我已经做到了验证低于溶液的结果。

Of course there is a brute force algorithm which calculates all possible of the heapified arrays and counts the number of exchanges for each one, and I have done that to verify the result of the solution below.

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

N = 2：显然，这是[2,1]

N=2: apparently, it's [2, 1]

N = 3：[3，X，1] 由于每个筛选通话将产生，顶多是一些 互换等于高度（其等于⌊log（n）的⌋（从 底部在其上筛分呼叫是由该节点的堆），所以 我们把1到阵列的末端。显然，X = 2。

N=3: [3, x, 1]. Since each sifting call will incur, at most, a number of swaps equal to the "height(which is equal to ⌊log(n)⌋" (from the bottom of the heap) of the node on which the sifting call is made, so we place 1 to the end of the array. apparently, x=2.

N = 4：[4，X，Y，1] 后第一提取物的最大，我们需要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=4: [4, x, y, 1] After first extract-max, we need heapify [1, x, y]. If we sift it to the case when N=3, [3, 2, 1], since this sifting operation incurs the most swaps which is equal to the "height", plus the maximal number of exchanges when N=3, so that's the scenario of maximal number of exchanges when N=4. Thus, we do the "siftDown" version of heapify backwards to [3, 2, 1]: swap 1 with its parent until 1 is the root. So x=2, y=3

N = N：N，A，B，C，...，X，1] 因此，通过归纳，我们做的N = N当一回事：后第一 提取-MAX，我们筛选下来[1，A，B，C，...，x]中的heapified阵列时，N = n-1个。所以我们这样做反了，得到了我们的东西。

N = n: [n,a,b,c,...,x,1] So, by induction, we do the same thing when N=n: after first extract-max, we sift down [1, a, b, c, ..., x] to the heapified array when N= n-1. So we do this backwards, get what we what.

下面是code的输出heapified阵列符合要求，当你输入N：

Here is the code that outputs the heapified array which meets the requirements when you input 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; }