【题目来源】
AcWing：838. 堆排序 - AcWing题库
【题目描述】
输入一个长度为\(n\)的整数数列，从小到大输出前\(m\)小的数。
【输入】
第一行包含整数\(n\)和\(m\)。第二行包含\(n\)个整数，表示整数数列。
【输出】
共一行，包含\(m\)个整数，表示整数数列中前\(m\)小的数。
【输入样例】
5 3
4 5 1 3 2
【输出样例】
1 2 3
【解题思路】
【算法标签】
《AcWing 838 堆排序》 #堆#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010;
int n, m; // n: 堆的大小，m: 要输出的最小值的数量
int h[N], siz; // h: 堆数组，siz: 当前堆的大小// 向下调整函数
void down(int u)
{int t = u; // t记录最小值的下标// 比较当前节点与其左子节点if (u * 2 <= siz && h[u * 2] < h[t]){t = u * 2;}// 比较当前节点与其右子节点if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]){t = u * 2 + 1;}// 如果最小值不是当前节点，交换并继续调整if (u != t){swap(h[u], h[t]);down(t);}
}int main()
{scanf("%d%d", &n, &m); // 读入n和mfor (int i = 1; i <= n; i++){scanf("%d", &h[i]); // 读入堆的元素}siz = n; // 初始化堆的大小// 建堆：从最后一个非叶子节点开始向下调整for (int i = n / 2; i; i--){down(i);}// 输出前m个最小值while (m--){printf("%d ", h[1]); // 输出堆顶（最小值）h[1] = h[siz]; // 用最后一个元素覆盖堆顶siz--; // 堆大小减1down(1); // 从堆顶开始向下调整}return 0;
}
【运行结果】
5 3
4 5 1 3 2
1 2 3