二項隊列的查找插入合并操作

源碼例如以下：

/*
<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(){
}