首先在一个完全二叉树里面
二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,就是完全二叉树
需要把这个二叉树存储在一维数组里面
那么假设一个数组q
q[1]就是是一个行的唯一一个数,这个位置就是数的根,也就是root
root有两个子节点,存储在q[2],q[3]中
同样的道理,这两个节点,每个节点都有两个子节点
我们可以发现q[n]的两个子节点是q[n*2]和q[n*2+1]
这样就可以把完全二叉树存储到一维数组了
现在输入了n个数据 for(int i=1;i<=n;i++)cin>>q[i];
1如何让他们有序
看这一行 for(int i=n/2;i;i--)down(i);
down(i)就是,从第i个节点开始往下检索,如果q[i]大于它的子节点,那么就交换它和它子节点的位置,交换完后继续比较,直到小于它的所有节点
void down(int u){ //idx是最后的元素的下标
int t=u; //先把u赋值给t
if(u*2<=idx&&q[u*2]<q[t])t=u*2; //如果它左边的子节点小于它,那么最小值目前是左边的节点
if(u*2+1<=idx&&q[u*2+1]<q[t])t=u*2+1 //它右边的子节点小于最小值,那么最小值是右边的节点
if(u!=t){ //说明它的子节点有比它小的
swap(q[u],q[t]);
down(t); //继续递归下一层,直到最后一层或者下面一层都比它大
}
}
2.最小值是怎么得出
经过1的操作之后,我们发现,这样的话,大的就在下面,小的就在上面了,那么最小的就一定在第一个位置,也就是q[1],所以我们输出q[1]
那么,现在输出了第一个小的,那么第二个小的如何输出?
我们需要先把q[idx]赋值给q[1],就是最后一个元素给第一个元素,这样的话对中间的排列没有影响,而且也方便减小最后一个元素,也就是直接idx--,就删去了最后一个元素,接下来,我们只需要down(1),让第一个元素进行一次全局比较,让全部元素重现有序,然后输出q[1],一直持续这个过程,就可以让所有元素有序
完整代码省略头文件
int q[100010],n,m,idx;
void down(int u){ //这个函数上面有解释
int t=u;
if(u*2<=idx&&q[u*2]<q[t])t=u*2;
if(u*2+1<=idx&&q[u*2+1]<q[t])t=u*2+1;
if(u!=t){
swap(q[u],q[t]);
down(t);
}
}
cin>>n;
int m=n; //一共输出n次
for(int i=1;i<=n;i++)cin>>q[i];
idx=n; //最大下标是n
for(int i=n/2;i;i--)down(i); //从倒数第二行开始一轮一轮让他们有序
while(m--){
cout<<q[1]<<" "; //输出目前最小值
q[1]=q[idx]; //最后元素到第一个
idx--; //删除最后的元素
down(1); //从第一个元素进行一轮比较,让最小值到第一个
}