开发笔记:838.堆排序相关知识整理

https://www.acwing.com/problem/content/840/


在进行down操作的时候&＃xff0c;只需要让根节点和它的左右儿子结点比较就可以了。

#include
#include
#include<iostream>
using namespace std;
const int N&＃61;1e5&＃43;10;
int a[N],cnt;
void down(int u)
{
int t&＃61;u;
if(u*2<&＃61;cnt&&a[u*2]<a[t]) t&＃61;u*2;//左儿子存在且小于根
if(u*2&＃43;1<&＃61;cnt&&a[u*2&＃43;1]<a[t]) t&＃61;u*2&＃43;1;//右儿子
if(u!&＃61;t)
{
swap(a[u],a[t]);
down(t);
}
}
int main(void)
{
int n,m; cin>>n>>m;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i];
cnt&＃61;n;
for(int i&＃61;n/2;i>&＃61;1;i--) down(i);// 从n/2 开始是因为最下面一层没有儿子&＃xff0c;故不需要down
//也可以理解为将所有的根节点down 因为 左 u*2 右 u*2&＃43;1 其根都是u 即 n/2
while(m--)
{
cout<<a[1]<<" ";
a[1]&＃61;a[cnt--];
down(1);
}
return 0;
}