找到一个heapified阵列将其转换为一个排序后的数组时，交换的总数为最大可能 [英] find a heapified array when converting it to a sorted array, the total number of exchanges is maximal possible

问题描述

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

Inspired by this post, I googled the worst case of heapsort and found this question on cs.stackexchange.com, 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;
}

这篇关于找到一个heapified阵列将其转换为一个排序后的数组时，交换的总数为最大可能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！