0838

838. 堆排序

题目

输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。

输入格式

第一行包含整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

输出格式

共一行，包含 $m$ 个整数，表示整数数列中前 $m$ 小的数。

数据范围

$1 \le m \le n \le 10^5$，

$1 \le 数列中元素 \le 10^9$

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

题解

前置题目：0240

前置知识：语法

本题知识：数据结构-堆

题目分析

// 建堆
for i := n / 2; i > 0; i-- {
    down(i)
}

                1               第 3 层
             /     \
            2       3           第 2 层
          /   \   /   \
         4    5   6    7        第 1 层
        /
       8                        第 0 层 

建堆的时间复杂度为什么是 O(n) 的？

设 n 是总结点数，

总的时间是 $\sum_{k=0}^{\log n} \frac{n}{2^{k+1}} k, \frac{n}{2^{k+1}}$ 是第 $\mathrm{k}$ 层需要比较的次数，比如说第 1 层有 n/4 个节点，每个节点需要下沉 1 次。

化简 $\sum_{k=0}^{\log n} \frac{n}{2^{k+1}} k=\sum_{k=0}^{\infty} \frac{n}{2^{k+1}} k=\sum_{k=0}^{\infty} \frac{k}{2^{k+1}} n$,，然后错位相减或者级数求和 $\sum_{n=0}^{\infty} n x^{n}=\frac{x}{(1-x)^{2}}, x<1$ 这个公式就得到 $\sum_{k=0}^{\infty} \frac{k}{2^{k+1}} < 1$

所以总的时间复杂度是小于 n 的，即是 O(n)