Heap模板 - #include <Seter> - using namespace Orz;
Heap模板
再来个模板，这个大家应该都会写，STL里面也有，但是自己写看起来爽一点。以前用递归实现的插入什么的，现在改成循环了，快了好多（废话）。
代码长度各种悲剧，SAP也就35行Heap快40行了……Heap操作多伤不起啊！
这个模板只测试过Update和Insert两个操作……错了不怪我 = =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <stdio.h>#include <string.h>#include <Seter>#define maxn 100000#define Type int#define TypeSize sizeof(Type)#define cmp(x,y) ((x)>(y))typedef struct _Heap{Type Value[maxn];int Size;}Heap,*PHeap;inline Swim(PHeap heap,int x){ Type t; for(memcpy(&t,heap->Value+x,TypeSize);x&&cmp(heap->Value[x-1>>1],t);x=x-1>>1)memcpy(heap->Value+x,heap->Value+(x-1>>1),TypeSize); memcpy(heap->Value+x,&t,TypeSize); return x;}inline Sink(PHeap heap,int x){ Type t;int c; for(memcpy(&t,heap->Value+x,TypeSize);(x<<1^1)<heap->Size;x=c){ c=(x<<1)+2==heap->Size?x<<1^1:cmp(heap->Value[x<<1^1],heap->Value[(x<<1)+2])?(x<<1)+2:x<<1^1; if(cmp(heap->Value[c],t))break; memcpy(heap->Value+x,heap->Value+c,TypeSize); }memcpy(heap->Value+x,&t,TypeSize); return x;}inline Insert(PHeap heap,Type x){ memcpy(heap->Value+heap->Size,&x,TypeSize); return Swim(heap,heap->Size++);}inline Update(PHeap heap,int i,Type x){ int flag=cmp(heap->Value[i],x); memcpy(heap->Value+i,&x,TypeSize); return flag?Swim(heap,i):Sink(heap,i);}inline void Remove(PHeap heap,int x){ Update(heap,x,heap->Value[--heap->Size]);}inline getint(){ int re=0,ch=getchar(),k; while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}main(){ return 0;} |
By Seter
2016年2月13日 23:34
21行。。。。
#include <stdio.h>
#include <string.h>
#include <Seter>
#define maxn 100000
#define cmp(x,y) ((x)>(y))
typedef struct _Heap{int Value[maxn];int Size;}Heap,*PHeap;
int memcpy1(void *dest, const void *src, size_t n){memcpy(dest,src,n);return 1;}
inline Swim(PHeap heap,int x,int t=0){
for(memcpy1(&t,heap->Value+x,sizeof(int));x&&cmp(heap->Value[x-1>>1],t);x=x-1>>1)memcpy1(heap->Value+x,heap->Value+(x-1>>1),sizeof(int));
return memcpy1(heap->Value+x,&t,sizeof(int)),x;}
inline Sink(PHeap heap,int x,int t=0,int c=0,int br=0){
for(memcpy1(&t,heap->Value+x,sizeof(int));!br&&(x<<1^1)<heap->Size;x=c)
c=(x<<1)+2==heap->Size?x<<1^1:cmp(heap->Value[x<<1^1],heap->Value[(x<<1)+2])?(x<<1)+2:x<<1^1,cmp(heap->Value[c],t)?br=1:memcpy1(heap->Value+x,heap->Value+c,sizeof(int));
return memcpy1(heap->Value+x,&t,sizeof(int)),x;}
inline Insert(PHeap heap,int x){return memcpy1(heap->Value+heap->Size,&x,sizeof(int)),Swim(heap,heap->Size++);}
inline Update(PHeap heap,int i,int x,int flag=0){return flag=cmp(heap->Value[i],x),memcpy1(heap->Value+i,&x,sizeof(int)),flag?Swim(heap,i):Sink(heap,i);}
inline void Remove(PHeap heap,int x){Update(heap,x,heap->Value[--heap->Size]);}
inline getint(int re=0,int ch=0,int k=0,int t=1){
while(t?t=0,ch=getchar():ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
return k?-re:re;}