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

朴灿烈づ我的快乐病毒、 2022-06-03 08:09 165阅读 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  
Hint  
请用堆排序完成。

Author  
xam

#include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    const int MAX = 15;
    int a[MAX];
    void swap(int &a, int &b)
    {
        int t;
        t = a;
        a = b;
        b = t;
    }
    void heapAdjust(int i, int n)
    {
        if (n == 0)return;
        if (i <= n / 2)//如果是叶节点就不用进行调整
        {
            int min = i;
            int lchild = i * 2;
            int rchild = i * 2 + 1;
            if (lchild <= n && a[min] > a[lchild])
                min = lchild;
            if (rchild <= n && a[min] > a[rchild])
                min = rchild;
            if (min != i)
            {
                swap(a[i], a[min]);
                heapAdjust(min, n);
            }
        }
    }
    void heapBuild(int n)
    {
        int i;
        for (i = n / 2; i >= 1; i--)//非叶节点最大序号为size/2
        {
            heapAdjust(i, n);
        }
    }
    void heapSort(int n)
    {
        int i;
        for (i = n; i >= 1; i--)
        {
            swap(a[1], a[i]);
            heapAdjust(1, i - 1);
        }
    }
    int main()
    {
        int n, m;
        scanf("%d %d", &n, &m);
        int i;
        for (i = 1; i <= m; i++)
            scanf("%d", &a[i]);
        heapBuild(m);
        int t;
        for (i = m + 1; i <= n; i++)
        {
            scanf("%d", &t);
            if (t > a[1])
            {
                a[1] = t;
                heapAdjust(1, m);
            }
        }
        heapSort(m);
        for (i = 1; i < m; i++)
            printf("%d ", a[i]);
        printf("%d\n", a[i]);
        return 0;
    }