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

 

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

Time Limit: 200 ms Memory Limit: 512 KiB

Problem Description

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

Input

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

Output

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

Sample Input

6 3
12 6 56 23 188 60

Sample Output

188 60 56

提示：本题要求用堆排来解决，堆排需要建大堆和小堆。堆排的时间复杂度是O(nlogn)

代码实现如下（gcc):

#include <stdio.h>
int a[20];
int m;

void Swap(int x,int y)//交换顺序
{
    int t;
    t=a[x];
    a[x]=a[y];
    a[y]=t;
}

void Siftdown(int i)//向下找
{
    int t,flag=0;//t用来记录较小结点，flag来判断能否向下调整
    while(i*2<=m&&flag==0)
    {
        if(a[i]>a[i*2])
            t=i*2;
        else
            t=i;
        if(i*2+1<=m)
        {
            if(a[t]>a[i*2+1])
                t=i*2+1;
        }
        if(t!=i)
        {
            Swap(t,i);//交换
            i=t;//向下更新
        }
        else
            flag=1;//否则不能调整了
    }
}

void heapsort()//堆排序
{
    while(m>1)
    {
        Swap(m,1);
        m--;
        Siftdown(m);
    }
}

int main()
{
    int num,n,i,j;
    scanf("%d %d",&num,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    n=m;
    for(i=m/2;i>=1;i--)
    {
        Siftdown(i);
    }
    for(i=m+1;i<=num;i++)
    {
        int x;
        scanf("%d",&x);
        if(x>a[1])
        {
            a[1]=x;
            for(j=m/2;j>=1;j--)
            {
                Siftdown(j);
            }
        }
    }
    heapsort();
    for(i=1;i<=n;i++)
    {
        i<n? printf("%d ",a[i]):printf("%d\n",a[i]);
    }
    return 0;
}


/***************************************************
Result: Accepted
Take time: 196ms
Take Memory: 156KB
****************************************************/