登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.2 二叉堆 › 二叉堆 / 搜索
JSON MD

2.2 二叉堆

Huffman 荷马史诗
42 行
CPP JSON
【Huffman(荷马史诗)】 代码包含 up, down, push, delet, in 等核心函数,实现了 Huffman 的算法逻辑。 核心函数: void up(Re p) — 核心算法函数 void down(Re p) — 核心算法函数 void push(Re x,Re d) — 压入元素 void delet(Re p) — 核心算法函数 void in(Re &x) — 核心算法函数 核心结构体:QAQ
C++ 41 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
LL ans,fu,S,d,k,n,t,i,x;
struct QAQ{LL x,d;inline bool operator<(QAQ b)const{return x==b.x?d<b.d:x<b.x;}}Q[100011];
inline void up(Re p){
	while(p>1)
		if(Q[p]<Q[p>>1])swap(Q[p],Q[p>>1]),p>>=1;
		else break;
}
inline void down(Re p){
	int s=p<<1;
	while(s<=t){
		if(s<t&&Q[s|1]<Q[s])s++;
		if(Q[s]<Q[p])swap(Q[s],Q[p]),p=s,s<<=1;
		else break;
	}
}
inline void push(Re x,Re d){Q[++t].x=x,Q[t].d=d;up(t);}
inline void delet(Re p){swap(Q[p],Q[t--]);down(p);}
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(fu)x=-x;
}
int main(){
	in(n),in(k);
	while(n--)in(x),push(x,0);
	while((t-1)%(k-1))push(0,0);
	while(t>1){
		x=k,S=0,d=0;
		while(x--)d=max(d,Q[1].d),S+=Q[1].x,delet(1);
		ans+=S,push(S,d+1);
	}
	printf("%lld\n%lld",ans,Q[1].d);
}
二叉堆 (Supermarket) 小根堆
47 行
CPP JSON
【二叉堆 (Supermarket)(小根堆)】 代码包含 cmp, CL, up, down, pop 等核心函数,实现了 二叉堆 (Supermarket) 的算法逻辑。 核心函数: bool cmp(QAQ a,QAQ b) — 核心算法函数 void CL(无参数) — 核心算法函数 void up(int p) — 核心算法函数 void down(int p) — 核心算法函数 void pop(无参数) — 弹出元素 int top(无参数) — 获取栈顶/堆顶元素 int size(无参数) — 获取大小/元素个数 void push(int x) — 压入元素 核心结构体:QAQ, QWQ
C++ 46 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct QAQ{int w,d;}a[10003];
int ans,n,i;
inline bool cmp(QAQ a,QAQ b){return a.d!=b.d?a.d<b.d:a.w>b.w;}
struct QWQ{
	int heap[10003],t;
	inline void CL(){memset(heap,0,sizeof(heap));t=0;}
	inline void up(int p){
		while(p>1)
			if(heap[p>>1]>heap[p])swap(heap[p],heap[p>>1]),p>>=1;
			else break;
	}
	inline void down(int p){
		int s=(p<<1);
		while(s<=t){
			if(s<t&&heap[s]>heap[s|1])s++;
			if(heap[s]<heap[p]){
				swap(heap[s],heap[p]);
				p=s,s<<=1;
			}
			else break;
		}
	}
	inline void pop(){delet(1);}
	inline int top(){return heap[1];}
	inline int size(){return t;}
	inline void push(int x){heap[++t]=x;up(t);}
	inline void delet(int p){swap(heap[p],heap[t--]);down(p);}
}Q;
int main(){
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].d);
        sort(a+1,a+n+1,cmp);ans=0;Q.CL();
        for(i=1;i<=n;i++)
            if(Q.size()<a[i].d)Q.push(a[i].w);
            else if(Q.top()<a[i].w)Q.pop(),Q.push(a[i].w);
        while(Q.size())ans+=Q.top(),Q.pop();
        printf("%d\n",ans);
    }
}
已复制