const int DefaultSize=30;
#include<iostream>
using namespace std;
struct item{    
        char data;
        int freq;        
    
};
item arr[27]={{'A',32},{'B',13},{'C',22},{'D',32},{'E',103},{'F',21},{'G',15},{'H',47},
{'I',57},{'J',1},{'K',5},{'L',32},{'M',20},{'N',57},{'O',63},{'P',15},{'Q',1},{'R',48},{'S',51},{'T',80},
{'U',23},{'V',8},{'W',18},{'X',1},{'Y',16},{'Z',1},{' ',168}};
class HTree;
class MinHeap;
void BuildHuffmanTree(item *fr,int n,HTree &newtree);
class HTreeNode{//树的结点定义
    friend class HTree;
    friend class MinHeap;
    public:
        item elem;// 结点数据域,freq为权值
        HTreeNode *leftChild,*rightChild;//结点左右子女指针
};
class HTree{
    public:
        HTreeNode *root;//扩充二叉树的根        
    public:
        HTree(){
            root=NULL;
        }
        HTree(HTree &bt1,HTree &bt2){//合并二叉树
            root->leftChild=bt1.root;
            root->rightChild=bt2.root;
            root->elem.freq=bt1.root->elem.freq+bt2.root->elem.freq;//合并后的权值
        }        
        //void In_order();
        ~HTree(){}
};
void BuildHuffmanTree(item *fr,int n,HTree &newtree){
    //输出n个频度数据fr[0]~fr[n-1],构造霍夫曼树,通过参数newtree返回,
    HTree first,second;     
    HTree Node[DefaultSize];//n棵树组成的森林
    
    if(n>DefaultSize){
        cerr<<"Size n  "<<n<<"exceeds the bondary of Array"<<endl;
        return;
    }
    for(int i=0;i<n;i++){
        Node[i].root->elem.freq=fr[i].freq;
        Node[i].root->elem.data=NULL;
        Node[i].root->leftChild=Node[i].root->rightChild=NULL;
    }
    MinHeap hp(Node,n);
    for(i=0;i<n-1;i++){
        hp.RemoveMin(&first);
        hp.RemoveMin(&second);
        newtree=new HTree( &first, &second);
        hp.Insert(&newtree);
    }
};
// 最小堆的定义
class MinHeap{
    private:
        HTree *heap;//存放最小堆元素的数组
        int CurrentSize;
        int MaxHeapSize;
        void FilterUp(int i);//从I到0自底向上进行调整成为最小堆
        void FilterDown(int i,int j);//从I到J自顶向下调整成为最小堆
    public:
        MinHeap(int size);//构造函数,空堆
        MinHeap(HTree arr[],int n);//构造函数
        ~MinHeap(){delete []heap;}
        void Insert(const HTree &x);//插入元素
        int RemoveMin(HTree &x);//删除最小元素
        int IsEmpty()const{
            return CurrentSize==0;
        }
        int IsFull()const{
            return CurrentSize==MaxHeapSize;
        }
        void MakeEmpty(){//置空堆
            Current=0;
        }
};
//构造函数,空堆
MinHeap::MinHeap(int size){
    MaxHeapSize=DefaultSize<size?size:DefaultSize;
    heap=new HTree[MaxHeapSize];
    if(heap==NULL){
        cerr<<"Memory Allocation Error!"<<endl;
        exit(1);
    }
    CurrentSize=0;
}
//构造函数
MinHeap::MinHeap(HTree arr[],int n){
    MaxHeapSize=DefaultSize<n?n:DefaultSize;
    heap=new HTree[MaxHeapSize];
    if(heap==NULL){
        cout<<"Memory Allocation Error!"<<endl;
        exit(1);
    }
    for(int i=0;i<n;i++){
        heap[i]=arr[i];            
    }
    CurrentSize=n;
    int CurrentPos=(CurrentSize-2)/2;//找到最初调整位置,最后的分支结点编号,
    while(CurrentPos>=0){            //自底向上逐步形成堆
        FilterDown(CurrentPos,CurrentSize-1);//局部自上向下调整
        CurrentPos--;                        //换一个分支结点
    }
}
//插入元素
void MinHeap::Insert(const HTree &x){
    if(IsFull()){
        cout<<"Heap Full;"<<endl;
        return ;
    }
    heap[CurrentSize]=x;
    FilterUp(CurrentSize);
    CurrentSize++;    
}
//删除堆顶元素
int MinHeap::RemoveMin(HTree &x){
    if(IsEmpty()){
        cout<<"Heap Empty!"<<endl;
        return 0;
    }
    x=heap[0];
    heap[0]=heap[CurrentSize-1];
    CurrentSize--;
    FilterDown(0,CurrentSize-1);
    return 1;
};
//从I到0自底向上进行调整成为最小堆
void MinHeap::FilterUp(int start){
    int j=start,i=(j-1)/2;
    HTree temp=heap[j];
    while(j>0){
        if(heap[i].root->elem.freq<=temp.root->elem.freq)
            break;
        else{
            heap[j]=heap[i];
            j=i;
            i=(i-1)/2;
        }
        heap[j]=temp;
    }
}
//从I到J自顶向下调整成为最小堆
void MinHeap::FilterDown(int start,int end){
    int i=start,j=2*i+1;
    HTree temp=heap[i];
    while(j<=end){
        if(j<end&&heap[j].root->elem.freq>heap[j+1].root->elem.freq)
            j++;
        if(temp.root->elem.freq<=heap[j].root->elem.freq)
            break;
        else{
            heap[i]=heap[j];
            i=j;
            j=2*j+1;
        }
        heap[i]=temp;
    }
}

int main(){
    HTree newtree;
    BuildHuffmanTree(arr,27,newtree);
    return 0;
}