写一个用到二叉堆(binary heap)的C++程序

来源:百度知道 编辑:UC知道 时间:2024/09/23 12:08:55
如题

/无向图最小生成树,prim算法+二叉堆,正向表形式,复杂度O(mlogm)
//返回最小生成树的长度,传入图的大小n和正向表list,buf
//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
//必须保证图的连通的!
#define MAXN 200
#define inf 1000000000
typedef double elem_t;
struct edge_t{
int to;
elem_t len;
};

#define _cp(a,b) ((a).d<(b).d)
struct heap_t{elem_t d;int v;};
struct heap{
heap_t h[MAXN*MAXN];
int n,p,c;
void init(){n=0;}
void ins(heap_t e){
for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);
h[p]=e;
}
int del(heap_t& e){
if (!n) return 0;
for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[p]=h[c],p=c,c<<=1);
h[p]=h[n--];return 1;
}
};

elem_t prim(int n,int* list,edge_t* buf,int* pre){
heap h;heap_t e;
elem_t min[MAXN],ret=0;
int v[MAXN],i,j;
for (i=0;i<n;i++)
min[i]=inf,v[i]=0,pre[i]=-1;
h.init(