堆排序
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N]; //h[]即为堆 heap 为了方便堆的下标从1开始
int size; //size为堆的大小
void down(int u)
{
int t=u;
/* 判断左右子树是否存在 由于是用完全二叉树存储
所以左子树为2x,右子树为2x+1 */
if(u*2<=size&&h[t]>h[2*u]) t=2*u; //这里的顺序是不可以颠倒的不然就不符合堆的定义
if(u*2+1<=size&&h[t]>h[2*u+1]) t=2*u+1; //注意这里h【】里面必须填的是t(在下面会提到)
//这和堆排序的定义有关 根小于左小于右
//所以优先比较的是左,如果左还比右小那么才选择将右上浮
//所以t的值必须先变化为左根的值才能进行比较
//我自己写的时候就忽略了第二步的比较 所以想写个题解分享一下
if(u!=t)
{
swap(h[u],h[t]);
down(t);
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
size=n;
for(int i=n/2;i;i--) //建堆
{
down(i);
}
while(m--)
{
cout<<h[1]<<' ';
h[1]=h[size]; //最小值由末尾的值覆盖
down(1); //此时1的位置 即根的位置已经是末尾的值,这个操作就是为将其回归原位
//而此时上浮的就是原序列中第二小的值
size--;
}
return 0;
}
我觉得优先比较左和右都没关系吧,比较两次后,肯定取的是左节点和右节点中的最小的那一个
u*2+1<=size这个条件不判断为什么会错。
判断右儿子是否存在,不存在就不用比