学步园

       优先队列式分支界限法解装载问题中需要用到最大堆MazHeap，但是书上没有给出代码，所以只能我们自己写了，下面我贴出这两个数据结构的代码，以供参考。解决了这两个数据结构，那么优先队列式分支界限法就很好实现了。

最大堆MaxHeap：

#include<iostream><br /> using namespace std;<br /> typedef struct Heap<br /> {<br /> int capacity;<br /> int size;<br /> int *Elem;<br /> }Heap,*HeapQueue;<br /> #define MaxData 32767<br /> HeapQueue init(int maxElem)<br /> {<br /> HeapQueue H;<br /> H=(HeapQueue)malloc(sizeof(Heap));<br /> H->capacity=maxElem;<br /> H->size=0;<br /> H->Elem=(int *)malloc((maxElem+1)*sizeof(int));<br /> H->Elem[0]=MaxData;<br /> return H;<br /> }<br /> void InsertMax(int x,HeapQueue H)<br /> {<br /> int i;<br /> for(i=++H->size;H->Elem[i/2]<x;i/=2)<br /> H->Elem[i]=H->Elem[i/2];//此时i还没有进行i/2操作<br /> H->Elem[i]=x;<br /> }<br /> int DeleteMax(HeapQueue H)<br /> {<br /> int i,child;<br /> int MaxElem,LastElem; //存储最大元素和最后一个元素。<br /> MaxElem=H->Elem[1]; //堆是从第1号元素开始的。<br /> LastElem=H->Elem[ H->size-- ]; //这里自动让size减少了。<br /> for(i = 1 ; i * 2 <= H->size ; i = child)<br /> {<br /> child=i * 2;<br /> /*在节点有左右子树的时候，可能存在一个大一个小的情况，这时候我们就要找出最小的；<br /> 如果Child = H->Size则表明他没有右子树，这时候就没有必要比较了。<br /> */<br /> if(child != H->size && H->Elem[child+1]>H->Elem[child])<br /> child++;//找最大的子树<br /> if(LastElem < H->Elem[child])<br /> H->Elem[i]=H->Elem[child];<br /> }<br /> H->Elem[i]=LastElem;<br /> return MaxElem;<br /> }<br /> void MakeEmpty(HeapQueue H)<br /> {<br /> H->size=0;<br /> }<br /> int FindMax(HeapQueue H)<br /> {<br /> return H->Elem[1];<br /> }<br /> void DestoryH(HeapQueue H)<br /> {<br /> free(H->Elem);<br /> free(H);<br /> }<br /> int main()<br /> {</p> <p> HeapQueue H=init(4);<br /> int i;<br /> for(i=1;i<=3;i++)<br /> InsertMax(i,H);<br /> /*<br /> cout<<H->size<<endl;<br /> for(i=1;i<=3;i++)<br /> cout<<H->Elem[i]<<endl;<br /> */<br /> int a=DeleteMax(H);<br /> cout<<a<<endl;<br /> return 1;<br /> }

最小堆MinHeap：

#include<iostream><br /> using namespace std;<br /> typedef struct Heap<br /> {<br /> int capacity;<br /> int size;<br /> int *Elem;<br /> }Heap,*HeapQueue;<br /> #define MinData -32767<br /> HeapQueue init(int maxElem)<br /> {<br /> HeapQueue H;<br /> H=(HeapQueue)malloc(sizeof(Heap));<br /> H->capacity=maxElem;<br /> H->size=0;<br /> H->Elem=(int *)malloc((maxElem+1)*sizeof(int));<br /> H->Elem[0]=MinData;<br /> return H;<br /> }<br /> void Insert(int x,HeapQueue H)<br /> {<br /> int i;<br /> for(i=++H->size;H->Elem[i/2]>x;i/=2)<br /> H->Elem[i]=H->Elem[i/2];//此时i还没有进行i/2操作<br /> H->Elem[i]=x;<br /> }<br /> int DeleteMin(HeapQueue H)<br /> {<br /> int i,child;<br /> int MinElem,LastElem;<br /> MinElem=H->Elem[1];//堆是从第1号元素开始的。<br /> LastElem=H->Elem[H->size--];//这里自动让size减少了。<br /> for(i = 1 ; i * 2 <= H->size ; i = child)<br /> {<br /> child=i * 2;<br /> /*在节点有左右子树的时候，可能存在一个大一个小的情况，这时候我们就要找出最小的；<br /> 如果Child = H->Size则表明他没有右子树，这时候就没有必要比较了。<br /> */<br /> if(child != H->size && H->Elem[child+1]<H->Elem[child])<br /> child++;<br /> if(LastElem>H->Elem[child])<br /> H->Elem[i]=H->Elem[child];<br /> }<br /> H->Elem[i]=LastElem;<br /> return MinElem;<br /> }<br /> void MakeEmpty(HeapQueue H)<br /> {<br /> H->size=0;<br /> }<br /> int FindMin(HeapQueue H)<br /> {<br /> return H->Elem[1];<br /> }<br /> void DestoryH(HeapQueue H)<br /> {<br /> free(H->Elem);<br /> free(H);<br /> }<br /> int main()<br /> {<br /> /*<br /> HeapQueue H=init(4);<br /> int i;<br /> for(i=1;i<=4;i++)<br /> Insert(i,H);<br /> int a=DeleteMin(H);<br /> cout<<a;<br /> */<br /> }

最大堆和最小堆也就该下大于号和小于号就可以了，贴出来是为了以后重用方便，省得到时再修改，麻烦。