5.堆

原题链接：102644.5.堆

Teng

2026-04-04 13:50:57

发布于：上海

14阅读

0回复

0点赞

小根堆：priority_queue< int,vector<int>,greater<int> > q;
大根堆：priority_queue< int,vector<int>,less<int> > q;

void put(int x){
	int pa,son;
	heap[++hs]=x;
	son=hs;
	while(son>1){
		pa=son/2;
		if(heap[son]>=heap[pa]) break;
		swap(heap[son],heap[pa]);
		son = pa;
	}
}

int get(){
	int num = heap[1];
	heap[1]=heap[hs--];
	int pa=1,son;
	while(pa*2<=hs){
		son=2*pa;
		if(son<hs && heap[son]>heap[son+1]) son++;
		if(heap[pa]<=heap[son]) break;
		swap(heap[pa],heap[son]);
		pa=son;
	}
	
	return num;
}