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