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

亦凉 2022-07-12 12:49 174阅读 0赞

think:  
1很快就要开学了，感觉有点舍不得，虽然有时候感觉做题做到崩溃，但是真的要开学后满满的都是舍不得，假期学习的氛围不是日常学习生活所能体验到的，那种效率虽然有时候感觉自己不在状态，但是还是要比日常的学习生活高，日常的学习生活精力很容易分散，之前读过一篇文章，说大学四年应该越过越简单，开始的时候，自己参加那么多活动，其实静心想一想，其中很多都是不必要的，不过自己还是不后悔居多吧，因为自己刚开始到大学的时候感觉不知道如何高效率的利用时间，因此竞选班委参加学生会就是想忙起来，那样不至于沉迷游戏荒废学业，慢慢的当自己开始想明白自己真正想要的是什么，就学着逐渐减少自己的精力分散，把精力集中起来，放在自己真正喜欢真正热爱，能够陪伴自己一辈子的事业上面，而不是面面俱到面面具弱，尝试去拥有自己擅长的能力领域  
2回归题目，题目一开始自己做的时候感觉用快排多好啊，然后自己不情不愿的照着书写了写堆排序的算法，然后提交之后要么超时要么超内存，然后就有点懵，然后自己又用快排写了写，结果还是超时，自己之前一直以为学会了快排函数基本就可以解决所有排序问题了，然后今天晚上发现自己有点无知加自大，自己问了问鑫哥然后又在网上搜了另一篇博客，感觉自己有不理解繁琐的结构框架，但当自己看到主函数中输入方式中用两个for循环输入，数组只开了一个比m大的数组的时候，有点触动，思想就是根据题意建立合适的最小堆，不用太大，在每次输入的时候和最小堆的堆顶比较，如果比堆顶大，那么就入堆，然后输入结束后将最小堆进行堆排序，然后输出前m项

[sdut原题链接][sdut]

数据结构实验之排序四：寻找大富翁  
Time Limit: 200MS Memory Limit: 512KB

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 <stdio.h>
    int h[14];
    int n;
    
    void swap(int x, int y);
    void siftdown(int i);
    void creat();
    void heapsort();
    int deletetop();
    
    int main()
    {
        int num, m, i, x;
        scanf("%d %d", &num, &m);
        n = m;
        for(i = 1; i <= m; i++)
            scanf("%d", &h[i]);
        creat();
        for(i = m+1; i <= num; i++)
        {
            scanf("%d", &x);
            if(x > h[1])
            {
                h[1] = x;
                siftdown(1);
            }
        }
        heapsort();
        for(i = 1; i <= m; i++)
            printf("%d%c", h[i], i == m? '\n': ' ');
        return 0;
    }
    
    void swap(int x, int y)
    {
        int t;
        t = h[x], h[x] = h[y], h[y] = t;
    }
    
    void siftdown(int i)
    {
        int t, flag = 0;
        while(i*2 <= n && flag == 0)
        {
            if(h[i] > h[i*2])
                t = i*2;
            else
                t = i;
            if(i*2 + 1 <= n)
            {
                if(h[t] > h[i*2+1])
                    t = i*2 + 1;
            }
            if(t != i)
            {
                swap(i, t);
                i = t;
            }
            else
                flag = 1;
        }
    }
    
    void creat()
    {
        int i;
        for(i = n/2; i >= 1; i--)
        {
            siftdown(i);
        }
    }
    
    void heapsort()
    {
        while(n > 1)
        {
            swap(n, 1);
            n--;
            siftdown(1);
        }
    }
    
    int deletetop()
    {
        int t = h[1];
        h[1] = h[n];
        n--;
        siftdown(1);
        return t;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 192ms
    Take Memory: 108KB
    Submit time: 2017-02-23 21:15:59
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2019/pid/3401