数据结构之排序之堆排序。寻找大富翁

素颜马尾好姑娘i 2022-06-10 12:38 167阅读 0赞

### 数据结构实验之排序四：寻找大富翁 ###

Time Limit: 200MS Memory Limit: 512KB

[Submit][] [Statistic][]

#### Problem Description ####

2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。

#### Input ####

首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。

#### Output ####

一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。

#### Example Input ####

6 3
    12 6 56 23 188 60

#### Example Output ####

188 60 56

#### 刚开开始了解堆排序，以为建立大顶堆时上层元素一定大于下层元素，这个理解是不对的，对于不是同一个根节点的孩子，是没有办法比较的，所以建立大顶堆小顶堆的过程只是找到最大的或者最小的元素，然后首元素与尾元素交换，重新调整堆，一直循环这个过程，最后实现排序。 ####

//这个题如果把全部元素堆排序，一定会超时，问了一下巨巨，因为输出元素比较少，所以不妨建一个m元素的小顶堆。让后来输入得元素一直与堆顶比较
    //比堆顶元素大，就入堆，然后重新调整堆，最后堆中的元素为前m大的元素，然后排序，输出。
    #include <stdio.h>
    #include <stdlib.h>
    void heapadjust(int a[],int i,int n)//建立小顶堆的过程
    {
        int j;
        int rc = a[i];//暂存当前根节点
        for(j = 2*i;j<=n;j*=2)//先指向其左孩子，顺子逐渐往下找
        {
            if(j<n&&a[j]>a[j+1])//进行第一次比较，左右孩子进行比较
                j++;//让j指向小的孩子
            if(rc<=a[j])//进行第二次比较，rc与小的孩子进行比较。
                break;//如果rc比小的孩子还小。说明rc就应该放在此时的根节点上。跳出循环，让a{i] = rc;
          a[i] = a[j];//否则，rc应该放在下面的位置，让a[i] = 小的孩子所对应的数，即a[j]
          i = j;//rc应该放在下面的位置,a[j]的值赋给了a[i]，所以，让此时的a[j]为a[i]，为新的根节点，继续比较。直到找到rc应该放的位置
        }
        a[i] = rc;
    }
    void heapsort(int a[],int m,int n)
    {
        int i,t;
        for(i = m/2;i>=1;i--)//从最下面的一个有孩子的节点开始，其下标为n/2，逐渐往上，建堆。
        heapadjust(a,i,m);//先建一个m个节点的小顶堆
        for(i = 1;i<=n-m;i++)//依次输入剩余的数，只要大于堆顶元素，就入堆，并重新调整堆。
        {
            int b;
            scanf("%d",&b);
            if(b>a[1])
                a[1] = b;
        heapadjust(a,1,m);//注意从最上面的开始调整。从下往上调整。
        }
        for(i = m;i>1;i--)
        {
            t = a[1];//a[1]此时为最小的元素，让a{n] 互换a[1]，然后剩余的n-1个元素重新调整堆结构。直到再次找到最小值。一直循环。最后变出来从大到小的排序了。
            a[1] = a[i];
            a[i] = t;
            heapadjust(a,1,i-1);
        }
    
    }
    int main()
    {
        int n,m,i;
        int a[20];
        scanf("%d%d",&n,&m);
        for(i = 1;i<=m;i++)//先建一个m个元素的小顶堆。
        {
            scanf("%d",&a[i]);
        }
        heapsort(a,m,n);
        for(i = 1;i<=m-1;i++)//输出
        {
            printf("%d ",a[i]);
    
        }
        printf("%d\n",a[m]);
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2218/pid/3401.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2218/pid/3401.html