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

堆排序：

堆排序利用了一维数组，思想简单但是现在还是不太熟练

先把前m个人排好之后，再排后面的！

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

Time Limit: 200 ms Memory Limit: 512 KiB

Submit Statistic

Problem De ion

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

Hint

请用堆排序完成

#include<bits/stdc++.h>
using namespace std;

int a[1000001];
void Cre_Heap(int a[], int i, int m)
{
    int t, q;
    t = i;

    while(2 * i <= m)
    {
        if(a[t] < a[2 * i])
        {
            t = 2 * i;
        }

        if(a[t] < a[2 * i + 1] && 2 * i + 1 <= m)
        {
            t = 2 * i + 1;
        }

        if(t != i)
        {
            q = a[t];
            a[t] = a[i];
            a[i] = q;
            i = t;
        }

        else
        {
            break;
        }
    }
}

void Jus_Heap(int a[], int i, int m)
{
    int t;
    while(m >= 1)
    {
        t = a[m];
        a[m] = a[1];
        a[1] = t;
        m--;
        Cre_Heap(a, 1, m);
    }
}

int main(void)
{
    int n, m, i, x;
    scanf(\"%d %d\", &n, &m);
    for(i = 1; i <= m; i++)
    {
        scanf(\"%d\", &a[i]);
    }

    for(i = m / 2; i >= 1; i--)
    {
        Cre_Heap(a, i, m);
    }
    Jus_Heap(a, 1, m);

    for(i = m + 1; i <= n; i++)
    {
        scanf(\"%d\", &x);
        if(a[1] < x)
        {
            a[1] = x;
            Cre_Heap(a, 1, m);
            Jus_Heap(a, 1, m);
        }
    }

    for(i = m; i >= 1; i--)
    {
        printf(\"%d%c\", a[i], i == 1 ?\'\\n\':\' \');
    }

    return 0;
}