堆排序不破坏原堆做法
针对y总代码中一次性的堆,参考海绵宝宝的代码,我写了一个不会破坏原堆并且
实现排序的堆排序,这样的排序时间复杂度上应该是$O(nlogn)$
主要思想
在原代码中,我们只对堆操作m次,我们如果在考虑时间成本的情况下
,可以也对我的这种代码操作m次,那么最后得到的结果就是只有
倒数m个数是被排好序的(因为我们每次都把最小的数放在size上)
但是如果不考虑时间成本,我们可以对堆操作n次,使其完全变为排好序的倒序数组
主要的操作就是:
swap(h[1],h[siz]);
这个操作会交换第一个和最后一个值,而不是直接把第一个值鲨掉,这样就不会有人死了
┏┛墓┗┓…(((m-__-)m
然后在每次循环中暂时不输出(当然要输出也可以,直接输出h[siz])
完整代码如下:
代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
const int N = 100010;
int h[N],siz;
void down(int u)
{
int t = u;
if(u * 2 <= siz && h[t] > h[u * 2]) t = u * 2;
if(u * 2 + 1 <= siz && h[t] > h[u * 2 + 1] ) t = u * 2 + 1;
if(t != u)
{
swap(h[u],h[t]);
down(t);
}
}
int main()
{
cin>>n>>m;
siz = n;
for(int i = 1; i <= n ; ++ i)
{
scanf("%d",&h[i]);
}
for (int i = n / 2; i ; i--)
{
down(i);
}
int op = 0;
int temp = n;
while(temp)
{
swap(h[1],h[siz]);
siz --;
down(1);
}
for(int i = n;i > n-m ;--i) cout<<h[i]<<" ";
return 0;
}