【SSL1271】排序I【堆】

【SSL1271】排序I【堆】

分析:

堆排序模板

s t l   C o d e : stl~Code: stl Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define reg register
using namespace std;
typedef long long ll;
priority_queue<int,vector<int>,greater<int> > q;
int n;
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		q.push(x);
	}
	while(!q.empty())
	{
		printf("%d ",q.top());
		q.pop();
	}	
	return 0;
}

手打堆 C o d e : Code: Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,a[N];
namespace Heap{
	void down(int x)
	{
		while(((x<<1)<=n&&a[x]>a[x<<1])||((x<<1|1)<=n&&a[x]>a[x<<1|1]))
		{
			int son=x<<1;
			if(son+1<=n&&a[son+1]<a[son]) son++;
			swap(a[x],a[son]);
			x=son;
		}
	}
	void up(int x)
	{
		while(x&&a[x]<a[x>>1])
		{
			swap(a[x],a[x>>1]);
			x>>=1;
		}
	}
	void pop(int x)
	{
		if(a[x]<a[n])a[x]=a[n--],down(x);
		else a[x]=a[n--],up(x);
	}
}
int main(){
	scanf("%d",&n);
	int size=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		Heap::up(i);
	}
	while(size--)
	{
		printf("%d ",a[1]);
		Heap::pop(1);
	}
	return 0;
}
上一篇:寒假集训二补题与题解


下一篇:洛谷 P1177 【模板】快速排序