题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N],sz;//定义一个数组为完全二叉树 ,sz表示节点个数
//表示借调换 向下调整,保证节点都是小于左右子树的
void down(int u){
int t=u;//令 t 表示三个点最小值
if(u*2<=sz&&h[u*2]<h[t]) t=u*2;
//如果左子树存在且左子树的值小于父节点 ,则更新t
if(u*2+1<=sz&&h[u*2+1]<h[t]) t=u*2+1;
//如果右子树存在且右子树的值小于父节点 ,则更新t
if(u!=t){//如果u !=t,说明根节点不是最小值
swap(h[u],h[t]);//交换
down(t);
}
}
int main(){
int n,m;
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--){//进行m次循环
cout<<h[1]<<' ';//每次输出根节点
h[1]=h[sz];//令最后一个数赋给根节点
sz--;//并删除最后一个数
down(1);//此时的根节点会向下调换,根节点会变成下一个数
}
return 0;
}
为什么下标要从1开始而不是0
因为完全二叉树被一个数组存储,但是二叉树的根节点,左子树和右子树分别用n,2n,2n+1表示,如果从0开始,那么他的根节点,左子树和右子树均为0
down(k)
将元素向下调换,每次将k作为父节点,与其左右子树进行比较,如果最小值不是k,则最小值与k互换
父节点一定是三个数中最小的
up(k)
将元素向上调换,每次将k作为又子树,与其父节点进行比较,如果小于父节点,则互换
for(int i=n/2;i;i–) down(i);//排列一下二叉树
i=n/2表示从最下面的非叶子节点开始,进行放置,然后运用down就可以排出二叉树
1.插到最后面,然后让他自己向前去调整位置,如果插到最前面,那么数组后面所有数的下标都要改变
2.根节点就是最小值
3.删除最小值,不仅要删元素,还要删下标,如果删的是最后的,那就可以直接删掉然后sz-1,
所以可以把最小的也就是根节点换到最后面方便操作下标的减少(即用最后的数覆盖根节点),最后在让根节点自己向下调换,其他的往前进位
4.删除任意一个数和删最小类似,二叉树中间某个数被删掉(即用最后的数覆盖根节点),最后判断是向下还是向上调换即可
5.将要修改的数赋给被修改的数,然后判断是向下还是向上调换即可