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

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

Hint

请用堆排序完成。
1 堆：完全二叉树，满足任何一个结点都小于等于其左右子结点（小顶堆）
或者满足任何一个结点都大于等于其左右子结点（大顶堆）。
2
堆排序的简单过程是：

1、根据序列，构建一个初始堆 （大根堆/小根堆）

2、交换堆的第一个和最后一个元素。

3、排除最后一个元素，将序列第一个到倒数第二个重新整理成 堆。

4、再次交换堆的第一个和最后一个元素

5、重复 第3 步

6 、重复上述过程直至完成排序

3如何判断建立小根堆还是建立大根堆？
顺序输出（从小到大）建立大根堆，逆序输出（从大到小）建立小根堆。
4

#include <stdio.h>
#include <stdlib.h>

int a[15];

void sort(int s, int m)//建立一个小顶堆。
{
    int key = s;
    int l = s*2;//左孩子；
    int r = s*2+1;//右孩子；
    if(s <= m/2)
    {
        if(l<= m && a[key] > a[l])//如果根比左子树根节点大，将左子树根节点让key保存
        {
             key = l;
        }
        if(r <= m && a[key] > a[r])//右子树根节点也是一样的
        {
              key = r;
        }
        if(s != key)//说明s被更换了
        {
            int t = a[s];a[s] = a[key];a[key] = t;//根节点与左或右节点进行交换
            sort(key, m);//r如果交换后下面也出现问题，则继续递归
        }
    }
}

int main()
{
    int n, m, i, d, x;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m; i++)//先输入m个元素去构建树
    {
         scanf("%d", &a[i]);
    }
    for(i = m/2; i > 0; i--)//将树变成小顶堆,因为m一半的位置就是具有左右结点的位置，所以要从m/2开始。
    {
        sort(i, m);
    }
    for(i = m+1; i <= n; i++)//再输入剩下的元素
    {
        scanf("%d", &x);
        if(x > a[1]) //如果输入的数比数中最小的大，则进行替换，然后再更成小顶堆。
        {
            a[1] = x;
            sort(1, m);
        }
    }
    for(i = m; i >= 1; i--) //将堆顶元素和当前未经排序子序列的最后一个元素交换
    {
        d = a[1];
        a[1] = a[i];
        a[i] = d;
        sort(1, i-1);//重复建小顶堆
    }//相当于每次把最小的移动到最后
    for(i=1;i<=m;i++)
    {
        if(i==m)
        {
            printf("%d\n",a[i]);
        }
        else
        {
            printf("%d ",a[i]);
        }
    }
    return 0;
}