テンプレート


ヒープは簡単で効率的なデータ構造であり、多くの一般的アルゴリズムの最適化において活躍している.
ヒープの定数はとても小さくて、同じデータで、ヒープで並べ替えて、速い列のスピードとほぼ同じですが、バランスツリーの速度はとても遅くて、Splayは2倍以上遅くなりました.
簡単に勉強して、テンプレートを出して、みんなと分かち合います.
CODE(ルートヒープ、並べ替え):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 200010
#define INF 0x7f7f7f7f
using namespace std;

struct SmallHeap{
	int num[MAX];
	int last;
	int Top() {
		return num[1];
	}
	void Insert(int x) {
		num[++last] = x;
		int now = last;
		while(num[now] < num[now >> 1] && now > 1)
			swap(num[now],num[now >> 1]),now >>= 1;
	}
	void Pop() {
		num[1] = num[last--];
		int now = 2;
		while(now <= last) {
			if(num[now] > num[now + 1])	++now;
			if(num[now] < num[now >> 1])	swap(num[now],num[now >> 1]),now <<= 1;
			else	break;
		}
	}
}heap;

int cnt;

int main()
{
	cin >> cnt;
	for(int x,i = 1;i <= cnt; ++i) {
		scanf("%d",&x);
		heap.Insert(x);
	}
	for(int i = 1;i <= cnt; ++i) {
		printf("%d
",heap.Top()); heap.Pop(); } return 0; }