堆排序
2021/6/18 16:16:00admin4994 阅读0 点赞2 评论
输入一个长度为 nn 的整数数列，从小到大输出前 mm 小的数。
输入格式
第一行包含整数 nn 和 mm。
第二行包含 nn 个整数，表示整数数列。
输出格式
共一行，包含 mm 个整数，表示整数数列中前 mm 小的数。
数据范围
1≤m≤n≤105\rm{1} \le m \le n \le {10^5}
1≤数列中的元素≤109\rm{1} \le 数列中的元素 \le {10^9}
输入样例
输出样例
题解
（堆） 完全二叉树 数据结构
如何手写一个堆？
| 操作 | 代码 |
|---|---|
| 插入一个数 | heap[++size] = x; up(size); |
| 求集合当中的最小值 | heap[1]; |
| 删除最小值 | heap[1] = heap[size]; size--; down(1); |
| 删除任意一个元素 | heap[k] = heap[size]; size--; down(k); up(k); |
| 修改任意一个元素 | heap[k] = x; down(k); up(k); |
up() 函数 O(logn)O(logn)：将当前元素与其父节点进行比较，若小于，则交换；
down() 函数 O(logn)O(logn)：将当前元素与其左、右子节点进行比较，若大于，则交换。
C++ 代码
CPP
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int heap[N], _size;
void down(int u)
{
int t = u;
if(u * 2 <= _size && heap[u * 2] <= heap[t])//与左节点比较
t = u * 2;
if(u * 2 + 1 <= _size && heap[u * 2 + 1] <= heap[t])//与右节点比较
t = u * 2 + 1;
if(u != t)
{
swap(heap[u], heap[t]);
down(t);//继续递归
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)//从1开始较为方便
cin >> heap[i];
_size = n;
for (int i = n >> 1; i; i--)//从倒数第二层开始down即可，最后一层不需要
down(i);
while(m--)
{
cout << heap[1] << ' ';//输出堆顶（最小元素）
heap[1] = heap[_size], _size--;//删除堆顶
down(1);
}
}
本题并不需要 up() 函数，故单独列出：
CPP
void up(int u)
{
while(u / 2 && heap[u / 2] > heap[u])
{
swap(heap[u / 2], heap[u]);
u /= 2;
}
}