【简单】堆排序
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m 。第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
\rm{1} \le m \le n \le {10^5}$``$\rm{1} \le 数列中的元素 \le {10^9}
输入样例
5 3
4 5 1 3 2输出样例
1 2 3题解
（堆） 完全二叉树 数据结构
如何手写一个堆？
操作 | 代码 |
|---|---|
插入一个数 | heap++size = x; up(size); |
求集合当中的最小值 | heap1; |
删除最小值 | heap1 = heapsize; size--; down(1); |
删除任意一个元素 | heapk = heapsize; size--; down(k); up(k); |
修改任意一个元素 | heapk = x; down(k); up(k); |
up() 函数 O(logn) ：将当前元素与其父节点进行比较，若小于，则交换；down() 函数 O(logn) ：将当前元素与其左、右子节点进行比较，若大于，则交换。
C++ 代码
#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() 函数，故单独列出：
void up(int u)
{
while(u / 2 && heap[u / 2] > heap[u])
{
swap(heap[u / 2], heap[u]);
u /= 2;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录