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

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

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

#include <stdio.h> int a[15]; void HeapAdjust(int s, int m)//建立一个小顶堆。 {     int key = s;     int lchild = s*2;//完全二叉树的左孩子；     int rchild = s*2+1;//完全二叉树的右孩子；     int d;     if(s <= m/2)     {         if(lchild <= m && a[key] > a[lchild])             key = lchild;         if(rchild <= m && a[key] > a[rchild])             key = rchild;         if(s != key)         {             d = a[s];             a[s] = a[key];             a[key] = d;             HeapAdjust(key, m);         }     } } int main() {     int n, m, i, d, x;     scanf("%d %d", &n, &m);     for(i = 1; i <= m; i++)         scanf("%d", &a[i]);     for(i = m/2; i > 0; i--)     {         HeapAdjust(i, m);//建造m个元素的小顶堆；     }     for(i = m+1; i <= n; i++)     {         scanf("%d", &x);         if(x > a[1]) /*随时替换小顶堆的根元素*/         {             a[1] = x;             HeapAdjust(1, m);/*重新将替根元素后的堆调成小顶堆*/         }     }     for(i = m; i >= 1; i--) /*将堆顶元素和当前未经排序子序列的最后一个元素交换*/     {         d = a[1];         a[1] = a[i];         a[i] = d;         HeapAdjust(1, i-1);/*重复建小顶堆*/     }     printf("%d", a[1]);     for(i = 2; i <= m; i++)         printf(" %d", a[i]);     return 0; }

转载于:https://www.cnblogs.com/CCCrunner/p/6444563.html

相关资源：JAVA上百实例源码以及开源项目