首页 > 代码库 > 二项队列的查找插入合并操作

二项队列的查找插入合并操作

源码例如以下:


/*
<span style="color:#ff0000;">一棵二次幂堆</span>是一棵左有序的堆,由右子树为空左子树为全然二叉树构成的根组成
<span style="color:#ff0000;">二项队列</span>:是二次幂堆的一个集合。 当中不存在相等大小的堆。其结构由队列节点数目确定
			相应整数的二进制表示。 
*/ 
#include <stdlib.h>
#include <stdio.h>
#define maxBQsize 40

typedef struct PQnode* PQlink;
typedef struct pq* PQ;
struct Item{int data;char c;};
struct PQnode{Item key;PQlink l,r;};
struct pq{PQlink *bq;};

PQlink z = NULL;
//连接两个大小相等的二次幂堆 
PQlink pair(PQlink p,PQlink q){
	if(p->key.data<q->key.data){
		p->r = q->l; q->l = p; return q; 
	} else{
		q->r = p->l; p->l = q; return p; 
	}
}

//插入操作
PQlink PQinsert(PQ pq, Item v){
	int i; PQlink c, t = (PQlink)malloc(sizeof *t);
	c = t, c->l = z; c->r = z; c->key = v;
	for(i=0;i<maxBQsize;i++){
		if(c==z)break;
		if(pq->bq[i] == z){
			pq->bq[i] = c; break;
		}
		c = pair(c,pq->bq[i]);pq->bq[i] = z;
	}
	return t;
}

//两个二项队列中的合并操作 
#define test(c,b,a) 4*(c) + 2*(b) + 1*(a)
void BQjoin(PQlink *a, PQlink *b){
	int i ; PQlink c = z;
	for(i=0;i<maxBQsize;i++)
		switch(test(c!=z,b[i]!=z,a[i]!=z)){
			case 2: a[i] = b[i];break;
			case 3: c=pair(a[i],b[i]);a[i]=c;break;
			case 4:	a[i]=c;c=z;break;
			case 5: c =pair(c,a[i]);a[i] = z; break;
			case 6:
			case 7: c = pair(c,b[i]);
		}
} 

//二项队列中删除最大元素的操作
Item PQdelmax(PQ pq){
	int i , max; PQlink x; Item v;
	PQlink temp[maxBQsize];
	for(i=0,max=-1;i<maxBQsize;i++)
		if(pq->bq[i]!=z)
			if(max==-1 || v.data<pq->bq[i]->key.data){
				max = i; v = pq->bq[max]->key;
			}
	x = pq->bq[max]->l;
	for(i=max;i<maxBQsize;i++) temp[i]=z;
	for(i=max;i>0;i--){
		temp[i-1]=x; x = x->r; temp[i-1]->r=z;
	}
	free(pq->bq[max]);pq->bq[max] = z;
	BQjoin(pq->bq,temp);
	return v;
}


main(){
}



二项队列的查找插入合并操作