题目描述

输入一个长度为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

算法1

堆排序

堆：维护一个数组集合
1.插入一个数 log(n)
2.求集合中的最小值 log(1)
3.删除最小值 log(n)
4.删除任意一个元素
5.修改任意一个元素
堆是一棵完全二叉树
小根堆：每一个点都小于等于左右儿子。根节点是最小值
存储：用一维数组来存。x的左儿子2x,右儿子2x+1
操作：down(x)x往下移,up(x)x往上移动,组合成上面5个操作。
下表从1开始。如果从0开始，则0的左儿子还是0，发生冲突

python 代码

def down(u):
    t = u           #t存储h[u],h[u*2],h[u*2+1]的最小值
    if u*2<=size and h[u*2]<h[t]:
        t=u*2
    if u*2+1<=size and h[u*2+1]<h[t]:
        t=u*2+1
    if u!=t:        #此时的t可能是左儿子也可能是右儿子
        h[u],h[t] = h[t],h[u]
        down(t)


if __name__ == "__main__":
    N = 100010
    h = [0]*N
    n,m = map(int,input().split())
    size=n
    h[1:n] = list(map(int, input().split()))
    for i in range(n // 2, 0, -1):  # 建堆O(n)复杂度，最后一层不需要down,从倒数第二层开始down,
        down(i)
    for i in range(m):
        print(h[1],end=" ")
        h[1]=h[size]
        size-=1                     #删除后size要减1
        down(1)