Heap模板 - #include <Seter> - using namespace Orz;

Heap模板

Seter posted @ 2011年8月26日 09:14 in Practice with tags Heap , 1901 阅读

再来个模板,这个大家应该都会写,STL里面也有,但是自己写看起来爽一点。以前用递归实现的插入什么的,现在改成循环了,快了好多(废话)。

代码长度各种悲剧,SAP也就35行Heap快40行了……Heap操作多伤不起啊!

这个模板只测试过Update和Insert两个操作……错了不怪我 = =

#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
1111111 说:
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;}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee