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

  • Z时代
  • 2024-01-10
  • 分类：问答

受本文的启发，我搜索了最坏的堆排序案例，并在cs.stackexchange.com上找到了这个问题，但是唯一的答案并没有真正回答这个问题，因此我决定自己进行研究。经过数小时的推理和编码，我已经解决了。我认为这个问题应归为SO，因此我将其张贴在这里。问题是要找到一个包含从1到n的不同数字的堆积数组，这样在将其转换为排序数组时，所有筛选操作中的交换总数最大可能。

回答：

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

  • 让我们从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时最大交换次数的场景。 到[

    ]：与其父级交换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;
}

以上是 在将其转换为排序数组时找到堆化数组，则交换的总数最大可能 的全部内容， 来源链接： utcz.com/qa/400552.html

回到顶部