题目描述
输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
输出格式
共一行,包含 m 个整数,表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤1e5,
1≤数列中元素≤1e9
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
基本操作
关于建堆:
i为什么从n/2开始down?
首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。
开始创建堆的时候,元素是随机插入的,所以不能从根节点开始down,而是要找到满足下面三个性质的结点:
1.左右儿子满足堆的性质。
2.下标最大(因为要往上遍历)
3.不是叶结点(叶节点一定满足堆的性质)
那这个点为什么时n/2?看图。
算法1
import java.io.*;
/**
* Created by Yolanda on 2021/6/15 14:33
*/
public class Main { //皆以小根堆为例
static int N=100010;
static int[] h=new int[N];
static int sizes;
static int n,m;
static void down(int u) //u为根节点,一个二叉树三点之中的父节点
{
int t=u;
if(u*2<=sizes&&h[u*2]<h[t]) t=u*2;//若根节点u的左儿子存在且左儿子的值小于当前min,则min下标为左儿子
if(u*2+1<=sizes&&h[u*2+1]<h[t]) t=u*2+1;//若根节点u的右儿子存在且右儿子的值小于当前min,则min下标为右儿子
if(u!=t) //如果u不是min
{
int temp=h[u];
h[u]=h[t];
h[t]=temp; //根节点u为min
down(t);//下沉递归
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] a=br.readLine().split(" ");
n=Integer.parseInt(a[0]);
m=Integer.parseInt(a[1]);
sizes=n;
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String[] b=br.readLine().split(" ");
for(int i=1;i<=n;i++)
h[i]=Integer.parseInt(b[i-1]);
for(int i=n/2;i>0;i--){
down(i); //O(n)建堆
}
while(m-->0)
{
System.out.print(h[1]+" "); //输出小根堆顶,即min
//删除小根堆顶:
h[1]=h[sizes];
sizes--;
down(1);
}
}
}
算法2
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N],sizes;
int n,m;
void down(int u) //u为根节点,一个二叉树三点之中的父节点
{
int t=u;//设t为min下标
if(u*2<=sizes&&h[u*2]<h[t]) t=u*2;//若根节点u的左儿子存在且左儿子的值小于当前min,则min下标为左儿子
if(u*2+1<=sizes&&h[u*2+1]<h[t]) t=u*2+1;//若根节点u的右儿子存在且右儿子的值小于当前min,则min下标为右儿子
if(u!=t) //如果u不是min
{
swap(h[u],h[t]); //根节点u为min
down(t);//下沉递归
}
}
int main()
{
scanf("%d%d",&n,&m);
sizes=n;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
//O(n)建堆:
for(int i=n/2;i;i--) down(i);
while(m--)
{
printf("%d ",h[1]);//输出小根堆顶,即min
//删除小根堆顶
h[1]=h[sizes];
sizes--;
down(1);
}
return 0;
}