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

堆排序：

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

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

?

?

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

Time Limit:?200 ms Memory Limit:?512 KiB

Submit Statistic

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

请用堆排序完成

#include

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 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,m);

}

Jus_Heap(a,m);

for(i = m + 1; i <= n; i++)

{

scanf("%d",&x);

if(a[1] < x)

{

a[1] = x;

Cre_Heap(a,m);

Jus_Heap(a,m);

}

}

for(i = m; i >= 1; i--)

{

printf("%d%c",a[i],i == 1 ?'n':' ');

}

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!