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
请用堆排序完成。
思路
因为时间的要求
所以我们采用堆排序
堆排序最坏的情况时间复杂度为：O(N*log2N)
堆排序的原理参考：
https://www.cnblogs.com/chengxiao/p/6129630.html
视频演示：
https://www.bilibili.com/video/av18980178?from=search&seid=419020408467955213
堆排序代码：
void heapsort(int arr[]){
//首先第一次调整大顶堆,从第一个非叶子节点，从右到左，从下到上
for(int i=m/2-1;i>=0;i--){//m 是数组元素个数
heapadjust(arr,i,m);
}
for(int i=m-1;i>0;i--){
swap(arr,0,i);
heapadjust(arr,0,i); //很明显i代表的是数组的长度
} //交换首末元素，然后再重新调整
}
void heapadjust(int arr[],int i,int len){
int temp=arr[i];
for(int k=2*i+1;k<len;k=2*k+1){//从子节点的左边开始，每一次迭代，都往下走一层
if(k+1<len&&arr[k]<arr[k+1]){//判断右子节点是否存在，且判断左子节点是否小于右子节点，是的话，k就指向右子节点
k++;
}
if(arr[k]>temp){
arr[i]=arr[k];
i=k;
}
else break;
}
arr[i]=temp;//这一步很好，减少了操作量，先不急着交换，因为已经知道下标和temp的值，我们到最后循环结束再放回来，就像快排里面的枢轴归位一样
}
代码分析：
1.堆排序重要几步：
>1.1 构建堆: 这一步其实就是一个数组，我们把这个数组看做一个堆(所以代码上没有什么内容)
>2.2 对堆进行第一次调整: 假设我们要从小到大排列，那么就构造一个大顶堆
>2.3 交换首末元素: 构造完大顶堆的意义就在于把最大的放到了根部，那么我们交换数组中第一个和最后一个，这样最后一个就是最大的
>2.4 再次进行调整: 这时我们舍弃数组的最后一个元素就好，针对前面几个再构建大顶堆
>2.构建大顶堆的代码分析：
>1.我们先从这个完全二叉树(堆)的第一个(从右到左，从下到上的顺序)非叶子节点开始，所谓非叶子结点，简单来讲就是指还具有分支的节点，你把堆看成一棵树，没有分支的节点就叫做叶子
公式就是: i=n/2-1
>2.接下来构造关于这个节点的大顶堆，我们要从它的左边的子节点开始，然后两个子节点比较，找到最大的，然后和这个节点比较，反正意思就是从这三个里面找到最大的那个，然后放在节点处
找子节点的公式 k=i/2+1
>3.然后就这样一步一步从右到左，从下到上构造，完成时，最大的就在顶部了
>4.当在最后一步，当构建第一个元素的顶堆时，我们要知道，它下面的几个元素的顶堆都是已经构造好了，唯一能破坏的就是，当这个元素小于它下面两个元素的其中一个时，交换，那么谁交换，i就指向了子节点的那个，然后再重新构造顶堆
好了，以上就是堆排序的主要内容，下面我们来看看这道题怎么破:
代码：
#include<stdio.h>
int a[12];
int m;
void heapsort(int arr[]);//long long 和 int的问题
void heapadjust(int arr[],int i,int len);
void swap(int arr[],int i,int j);
int main(){
int n;
int k=0;
int temp;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) {//注意题目要求，我们根本就不需要对n个数据进行排序，因为我们最后只要输出不大于10个的人数就行了
scanf("%d",&temp);
if(k<m)
a[k++]=temp;//先把m个数据读完了
else
{
int min=0;
for(int i=1;i<m;i++)
if(a[min]>a[i])
min=i;//找出m个里面最小的
if(a[min]<temp)
a[min]=temp;//把最小的踢掉
}
}
heapsort(a);
for(int i=m-1;i>0;i--)
printf("%d ",a[i]);
printf("%d",a[0]);
printf("\n");
}
void heapsort(int arr[]){
//首先第一次调整大顶堆,从第一个非叶子节点，从右到左，从下到上
for(int i=m/2-1;i>=0;i--){
heapadjust(arr,i,m);
}
for(int i=m-1;i>0;i--){
swap(arr,0,i);
heapadjust(arr,0,i);
} //交换首末元素，然后再重新调整
}
void heapadjust(int arr[],int i,int len){
int temp=arr[i];
for(int k=2*i+1;k<len;k=2*k+1){//从子节点的左边开始，每一次迭代，都往下走一层
if(k+1<len&&arr[k]<arr[k+1]){//判断右子节点是否存在，且判断左子节点是否小于右子节点，是的话，k就指向右子节点
k++; //这个地方考虑到后面k再怎么往下走一层的问题，就有点难度了，但是大顶堆性质 还是不变，只是换了个形式，可能跟算法时间复杂度有关？
}
if(arr[k]>temp){
arr[i]=arr[k];
i=k;
}
else break;
}
arr[i]=temp;//这一步很好，减少了操作量，先不急着交换，因为已经知道下标和temp的值，我们到最后循环结束再放回来，就像快排里面的枢轴归位一样
}
void swap(int arr[],int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
/*
Author : kevis
Status: accepted
Time:188ms
Memery:152kib
*/
是不是认为我们只要对所有的输入进行一个排序就好了？
如果这样做的话，我们看看数据最多有10^6个，再快的排序，也不可能在200ms时间内把这些数据排好
所以我们要做一个小trick：
题目要求是只要前十个就好了，那么我们先把这些数据里面的前十个找出来就好了，也就是说，我们创建一个10个元素的数组，然后把这些数据里面的最大的十个没有顺序的放到这个数组里面，这样子我们很快就得到了前十个，然后对这个10个进行排序就好了
这是一种很重要的思想！！！
如果排序的话，我们要对庞大的数据反反复复操作多次，而如果只要找最大那几个的话，我们只需要遍历一遍这些数据就好。
比如说我找一个最大的，那就一个个比，然后遍历一遍就能找到最大的，找两个最大的，就从输入里面得到一个数，然后遍历两个元素的数组，找到最小的那个，然后和输入的比较，然后看情况交换，这样子我们就可以忽略对那些小的元素的重复操作
注意我们要知道数组里面最小的那个再和输入比较，不是把输入直接和元素比较，然后小的话就交换，这样子是可能找不到最大的几个的
问题：
1.我们能用快排吗（为什么要用堆排序）
2.但是如果我们要找前1000个，或者更大，时间开销肯定会变大，有没有一个临界点就是我直接排序比先找到前几个会更好呢？
网友评论