二项堆算法基础篇（二）

View Code
  1 // 二项堆.cpp : 定义控制台应用程序的入口点。
  2 //
  3 /***********************************************************
  4 
  5 二项堆，算法数据结构复习
  6 
  7 Designer By cslave
  8 
  9 
 10 
 11 **************************************************************/
 12 
 13 
 14 #include "stdafx.h"
 15 #include <stdio.h>
 16 #include <stdlib.h>
 17 #include <iostream>
 18 using namespace std;
 19 #define MaxTrees 14
 20 #define INF (30000L)
 21 #define Capacity (16383)
 22 #define FatalError(Str) fprintf(stderr,"%s\n",Str),exit(1)
 23 typedef int ElementType ;
 24 typedef struct BinNode* Position;
 25 typedef struct BinNode* BinTree;
 26 struct BinNode                        //二项堆树节点
 27 {
 28     ElementType Element;                     
 29     Position    LeftChild;            
 30     Position    NextSibling;
 31 };
 32 struct Collection                     //二项堆
 33 {
 34     int CurrentSize;
 35     BinTree TheTrees[MaxTrees];
 36 };
 37 
 38 typedef struct Collection* BinQueue;       //二项堆类型的指针
 39 
 40 bool IsEmpy(BinQueue H)                //二项堆是否为空 即是否含有节点       
 41 {
 42     return H->CurrentSize==0;
 43 }
 44 
 45 bool IsFul(BinQueue H)                //二项堆是否为满，即节点数是否满载
 46 {
 47     return H->CurrentSize==Capacity;
 48 }
 49 
 50 BinQueue Initialize()                   //二项堆初始化          
 51 {
 52     BinQueue H;
 53     int i ;
 54     H=(BinQueue)malloc(sizeof (struct Collection));
 55     if(H==NULL)
 56     FatalError("out of space");
 57     H->CurrentSize=0;
 58     for(i=0;i<MaxTrees;i++)
 59         H->TheTrees[i]=NULL;           //初始化每一个二项堆树节点为空
 60     return H;
 61 }
 62 
 63 void DestroyTree(BinTree T)             //二项堆树节点的析构
 64 {
 65     if(T!=NULL)
 66     {
 67         DestroyTree(T->LeftChild);
 68         DestroyTree(T->NextSibling);
 69         free(T);
 70     }
 71 }
 72 
 73 void Destroy(BinQueue H)               //二项堆的析构
 74 {
 75     int i;
 76     for(i=0;i<MaxTrees;i++)
 77         DestroyTree(H->TheTrees[i]);
 78 }
 79 
 80 
 81 BinQueue MakeEmpty(BinQueue H)  //二项堆的置空
 82 {
 83     int i;
 84     Destroy(H);
 85     for(i=0;i<MaxTrees;i++)
 86         H->TheTrees[i]=NULL;
 87     H->CurrentSize=0;
 88     return H;
 89 }
 90 
 91 BinTree CombineTrees(BinTree T1,BinTree T2) //子二项树的合并
 92 {
 93     if(T1->Element>T2->Element)
 94         return CombineTrees(T2,T1);       //调整节点，根较小的二项树作为主合并点
 95     T2->NextSibling=T1->LeftChild;        //二项堆为了快速找出根的子树，采用的是左孩子，右兄弟存储策略 将小根的左孩子作为大根的右兄弟
 96     T1->LeftChild=T2;                    //将大根作为小根的左孩子
 97     return T1;
 98 }
 99 
100 BinQueue Merge(BinQueue H1,BinQueue H2)  //子二项树的合并
101 {
102     BinTree T1,T2,Carry=NULL;                               
103     int i,j;
104     if(H1->CurrentSize+H2->CurrentSize>Capacity)   //边界判定
105         FatalError("Node Num too large!");
106     H1->CurrentSize+=H2->CurrentSize;               
107     for(i=0,j=1;j<=H1->CurrentSize;i++,j*=2)   //j作为判定条件，判断二项堆可以合并为几阶
108     {
109         T1=H1->TheTrees[i];                     //抽取对等子二项树树根
110         T2=H2->TheTrees[i];
111         switch(!!T1+2*!!T2+4*!!Carry)         //此处用法很巧妙 1  ！！取一个数的布尔真值  2 我们用三个变量的二进制三位码表征八种情况
112         {
113         case 0:                             //没有子二项树
114         case 1:break;                        //只有T1 因为我们返回H1 所以什么都不用做。
115         case 2:                             //只有T2，我们仅需将T2赋值给H1即可
116             H1->TheTrees[i]=T2;
117             H2->TheTrees[i]=NULL;
118             break;
119         case 4:                              //上一阶二项树有合并到本阶 ，本阶无二项树
120             H1->TheTrees[i]=Carry;
121             Carry=NULL;
122             break;
123         case 3:                          //本阶两堆都有要合并的子二项树，则产生高阶进位
124             Carry=CombineTrees(T1,T2);
125             H1->TheTrees[i]=H2->TheTrees[i]=NULL;    
126             break;
127         case 5:                           //有低阶来的进位，同时又自身的T1 则合并进位和T1
128             Carry=CombineTrees(T1,Carry);
129             H1->TheTrees[i]=NULL;
130             break;
131         case 6:                           //  有低阶来的进位，同时又自身的T2 则合并进位和T2
132             Carry=CombineTrees(T2,Carry);
133             H2->TheTrees[i]=NULL;
134             break;
135         case 7:                          //此处尚有迷惑，我个人感觉因该是先Tmp=Carry; Carry=CombineTrees(T1,T2);H1->TheTrees[i]=Tmp
136             H1->TheTrees[i]=Carry;
137             Carry=CombineTrees(T1,T2);
138             H2->TheTrees[i]=NULL;
139             break;
140         }
141 
142     }
143     return H1;
144 }
145 
146 
147 BinQueue insert(BinQueue H,ElementType X) //节点的插入，在二项堆插入节点值X 
148 {
149     BinQueue TmpQue;
150     BinTree NewNode;
151     NewNode=(BinTree)malloc(sizeof(struct BinNode));
152     if(NewNode==NULL)
153         FatalError("memory insufficient!");
154     NewNode->Element=X;
155     NewNode->LeftChild=NULL;
156     NewNode->NextSibling=NULL;
157     TmpQue=Initialize();
158     TmpQue->CurrentSize=1;
159     TmpQue->TheTrees[0]=NewNode;          //创建仅含一个树节点的二项堆再与原来的堆做合并操作
160     return Merge(H,TmpQue);
161 }
162 
163 ElementType DeleteMin(BinQueue H)        //删除二项堆最小元素
164 {
165     int i,j;
166     int MinTree;
167     BinQueue DeleteQueue;
168     Position DeleteTree,OldRoot;
169     ElementType MinItem;
170     if(IsEmpy(H))
171     {
172         FatalError("BinQueue is Empty!");
173         return -INF;
174     }
175     MinItem= INF;
176     for(i=0;i<MaxTrees;i++)           //由二项堆性质可知，二项堆最小元素必然在每一个二项树的树根
177     {
178         if(H->TheTrees[i]&&H->TheTrees[i]->Element<MinItem) //找到并保存二项堆的最小值和索引i
179         {
180             MinItem=H->TheTrees[i]->Element;
181             MinTree=i;
182         }
183     }
184     DeleteTree=H->TheTrees[MinTree];      
185     OldRoot=DeleteTree;
186     DeleteTree=DeleteTree->LeftChild; //指向左儿子
187     free(OldRoot);
188     DeleteQueue=Initialize();        //初始化一二项堆
189     DeleteQueue->CurrentSize=(1<<MinTree)-1; //更新堆元素个数
190     for(j=MinTree-1;j>=0;j--)
191     {
192         DeleteQueue->TheTrees[j]=DeleteTree;//将左儿子作为堆的小一阶二项树
193         DeleteTree=DeleteTree->NextSibling;        //将左儿子的右兄弟作为下一个处理对象
194         DeleteQueue->TheTrees[j]->NextSibling=NULL; //处理后将二项树根节点右兄弟置空
195     }
196     H->TheTrees[MinTree]=NULL;//已经处理完最小树，将该树在堆数组中的元素置空
197     H->CurrentSize-=DeleteQueue->CurrentSize+1;//从原始堆中减去处理掉的二项树元素个数，加1是因为还有二项树根我们删除了
198     Merge(H,DeleteQueue);//合并H和新二项堆。
199     return MinItem;
200 
201 
202 
203 }
204 
205 
206 
207 
208 
209  
210 
211 
212 
213 
214 
215 int _tmain(int argc, _TCHAR* argv[])
216 {
217     ElementType arr[8]={12,24,21,65,14,16,18,26};
218     BinQueue H=Initialize();
219     for(int i=0;i<8;i++)
220         insert(H, arr[i]);
221     for(int j=0;j<8;j++)
222         cout<<DeleteMin(H)<<" ";
223     
224     return 0;
225 }
二项堆 算法基础篇（二）

二项堆算法基础篇（二）
