题目描述
输入一个长度为n的整数数列,从小到大输出前m小的数。
堆排序
样例
输入
5 3
4 5 1 3 2
输出
1 2 3
算法实现
思路
选取数组中前m个数,建立一个大根堆,然后让根节点元素和后面的元素挨个比较,如果小于根节点,就替换,然后再重新调整堆。最后输出这个堆
时间复杂度 O(nlogn)
Java代码
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));
String[] s=reader.readLine().split(" ");
int n=Integer.valueOf(s[0]), m=Integer.valueOf(s[1]);
int[] b=new int[m];//想让数组中前m个数建立一个大根堆
int[] a=new int[n-m];
String[] s1=reader.readLine().split(" ");
for(int i=0;i<m;i++){
b[i]=Integer.valueOf(s1[i]);
}
for(int i=0;i<n-m;i++){
a[i]=Integer.valueOf(s1[i+m]);
}
//前m个数建立大根堆
for(int i=m/2-1;i>=0;i--){
buildHeap(b,i,m-1);
}
//后面的数挨个与根节点元素比较,比他小就替换(加入堆中)
for(int i=0;i<n-m;i++){
if(a[i]<=b[0]){
b[0]=a[i];
//重新调整堆
buildHeap(b,0,m-1);
}
}
//此时堆中的元素就是前m个最小的,取值,每次将堆顶元素和数组末尾元素交换,然后再调整堆
for(int i=b.length-1;i>=0;i--){
swap(b,0,i);
buildHeap(b,0,i-1);
}
for(int i=0;i<m;i++){
writer.write(b[i]+" ");
}
writer.flush();
writer.close();
reader.close();
}
public static void buildHeap(int[] arr,int root,int length){
int left=root*2+1;
int right=root*2+2;
int max=root;
if(left<=length&&arr[max]<=arr[left]){
max=left;
}
if(right<=length&&arr[max]<=arr[right]){
max=right;
}
if(root!=max){
swap(arr,root,max);
buildHeap(arr,max,length);
}
}
public static void swap(int[] arr,int i,int j){
int t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}