?? huffman.h
字號:
typedef int ElemType ;
typedef struct node {
ElemType data;
struct node *lchild;
struct node *rchild;
} Btree;
Btree maketree(Btree &First, Btree &Second){
Btree merger;
merger.data=First.data+Second.data;
merger.lchild=&First;merger.rchild=&Second;
return merger;
}
template<class Type> class MinHeap{
public :
MinHeap(int ); // 建立空堆
MinHeap(Type arr[],int n); //建立以arr[]為元素的堆
~MinHeap(){delete []heap;};
int Insert(Type &x);
int RemoveMin(Type &x); //刪除堆頂元素
int IsEmpty()const {return CurrentSize == 0;}
int IsFull() const {return CurrentSize == MaxHeapSize;}
private:
enum {DefaultSize = 10};
Type *heap; //存放最小堆中元素的數組!
int CurrentSize; //當前堆中元素的個數
int MaxHeapSize; //允許存放最多個數
void FilterDown(int i,int m); //自頂向下調整
void FilterUp(int i); //從底向上調整
};
template<class Type> MinHeap<Type> :: MinHeap(int maxSize){
MaxHeapSize = DefaultSize< maxSize ? maxSize : DefaultSize;
heap=new Type[MaxHeapSize];
CurrentSize = 0;
} ;
template<class Type> MinHeap<Type> :: MinHeap(Type arr[],int n){
MaxHeapSize = DefaultSize< n ? n : DefaultSize;
heap=new Type[MaxHeapSize];
heap=arr; CurrentSize = n;
int currentPos = ( CurrentSize - 2)/2;
while (currentPos>=0){
FilterDown(currentPos,CurrentSize - 1);
currentPos --;
}
} ;
template<class Type> void MinHeap<Type> :: FilterDown(const int start,const int End){
int i=start,j=2*i+1;Type temp=heap[i];
while(j <= End){
if(j < End&&heap[j].data>heap[j+1].data)j++;
if(temp.data<=heap[j].data)break;
else{heap[i]=heap[j]; i=j; j=2*j+1;}
}
heap[i]=temp;
};
template<class Type> void MinHeap<Type> :: FilterUp(const int start){
int j=start,i=(j-1)/2;Type temp = heap[j];
while(j>0) {
if(heap[j].data>=heap[i].data)break;
else{ heap[j]=heap[i]; heap[i]= temp; j=i;i=(j-1)/2;}
}
};
template<class Type> int MinHeap<Type> :: Insert( Type &x){
if(CurrentSize==MaxHeapSize) {cerr << "Heap full"<<endl;return 0;}
heap[CurrentSize]=x; FilterUp(CurrentSize);
CurrentSize++;
return 1;
};
template <class Type> int MinHeap<Type> :: RemoveMin(Type &x){
if(!CurrentSize){cout<<"Heap empty"<<endl;return 0;}
x=heap[0]; heap[0]=heap[CurrentSize-1];
CurrentSize--;
FilterDown(0,CurrentSize - 1);
return 1;
};
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -