堆排序

题目

输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数，表示整数数列。
输出格式
共一行，包含m个整数，表示整数数列中前m小的数。
数据范围
1≤m≤n≤10 ^ 5，1≤数列中元素≤10 ^ 9
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

分析

STL库函数里有堆，STL里的堆就是优先队列，这里是用数组模拟一个堆。
对于堆来说 ，最好是从 1 开始，如果一个数的下标是x，那么下标是2x的就是它的左儿子，下标是2x+1的就是它的右儿子，这个题维护的是一个小根堆，即父节点的值小于等于左右儿子的值
heap[1]就是最小值，如果要删除堆顶则是将heap[size]的值赋给heap[1]，然后将heap[1]向下调。

当最初开始建堆的时候可以从n/2的时候执行一遍down(i)操作，这样的建堆方式的时间复杂度是O(n)的

代码

#include<iostream>
#include<algorithm>
using namespace std;
int si,heap[123456];
  //如果一个数变大了就要把他往下调
void down(int x) //这里x指的是下标
{
    int t=x;
    if(2*x<=si&&heap[t]>heap[2*x]) t=2*x;//如果大于左儿子，那么就让t等于左儿子下标
    if(2*x+1<=si&&heap[t]>heap[2*x+1]) t=2*x+1;//如果大于右儿子，就让t等于右儿子下标
    if(t!=x) 
    {
        swap(heap[x],heap[t]);
        down(t);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    si=n;
    for(int i=1;i<=n;i++) cin>>heap[i];
    for(int i=n/2;i;i--) down(i);
    while(m--)
    {
        cout<<heap[1]<<" ";
        heap[1]=heap[si];
        si--;
        down(1);
    }
    return 0;
}