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

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

TimeLimit: 200MS Memory Limit: 512KB

SubmitStatistic

PRoblemDescription

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

Input

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

Output

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

ExampleInput

63

126 56 23 188 60

ExampleOutput

18860 56

Hint

请用堆排序完成。 

Author

xam

#include <stdio.h>   //头文件只有一个防超时int h[1000002];//用来存放堆的数组int m;     //堆的大小//交换函数，用来交换堆中的两个元素的值void Swap(int x, int y){    int t;    t = h[x];    h[x] = h[y];    h[y] = t;}//向下调整函数void Siftdown(int i)  //传入一个需要向下调整的节点的编号i，这里传入1，即//从堆顶开始向下调整；{    int t, flag=0;   //flag用来标记是否需要继续向下调整    //当i结点有孩子（其实是至少有左孩子）并且有需要继续调整的时候循环就执行    while(i*2 <= m && flag == 0)    {        //首先判断它和左孩子的关系，并用t记录值较小的结点的编号        if(h[i] > h[i*2])            t = i*2;        else            t = i;        //如果它有右孩子，再对右孩子进行讨论        if(i*2+1 <= m)        {            //假如右孩子的值更小，更新较小的节点编号            if(h[t] > h[i*2+1])                t = i*2+1;        }        //如果发现最小的结点编号不是自己，说明子节点中有比父节点更小的        if(t != i)        {            Swap(t, i);   //交换他们            i = t;        //更新i为刚才与它交换的孩子结点的编号，便于接下来继续向下调整        }        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", &h[i]);    n = m;    for(i = m/2; i >= 1; i--)    //建m个元素的最小堆        Siftdown(i);    for(i = m+1; i <= num; i++)  //然后从第m+1个元素开始，与堆顶元素比较，        //如果比堆顶的元素小，那这个数就不要了，    {        int x;        scanf("%d", &x);        if(x > h[1])        {            //如果比堆顶的元素大，那就舍弃当前堆顶而            //将这个数作为新的堆顶，并维护最小堆的性质            h[1] = x;            for(j = m/2; j >= 1; j--)//可以改进把此行删除                Siftdown(j);        }    }    heapsort();              //堆排序    for(i = 1; i <= n; i++)        if(i != n)            printf("%d ", h[i]);        else            printf("%d/n", h[i]);    return 0;}/*求前k个最大的数则建立k个数的最小堆求前k个最小的数则建立k个数的最大堆算法描述：我们首先取这N个元素中的前K个元素来建立一个由K个元素组成的小（大）顶堆，这样堆顶元素便是当前已读取元素中的第K大（小）者；然后，依次读取剩下的N-K个元素，而对于其中的每个元素x，若x大于（小于）当前的堆顶元素，则将堆顶元素替换为x，并自堆顶至向下调整堆；这样，在读取完所有元素后，堆中的K个元素即为这N个数中的前K个最大（小）元素，同时堆顶元素为这N个数中的第K大（小）元素。*//***************************************************User name: jk160505徐红博Result: AcceptedTake time: 192msTake Memory: 104KBSubmit time: 2017-02-23 19:12:43****************************************************/