今天学习了堆排序
模板
int h[N], sz;//h[N]是有一维数组建立之后的堆
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[t] > h[u * 2]) t = u * 2;
if (u * 2 + 1 <= sz && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
if (u != t)
{
swap(h[t], h[u]);
down(t);
}
}
例题
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], sz;//h[N]是有一维数组建立之后的堆
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[t] > h[u * 2]) t = u * 2;
if (u * 2 + 1 <= sz && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
if (u != t)
{
swap(h[t], h[u]);
down(t);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
sz = n;
for (int i = n / 2; i; i--) down(i);
while (m--)
{
printf("%d ", h[1]);
h[1] = h[sz--];
down(1);
}
}