minheap.h

huffman 算法 包含的主要个文件： minheap.h:初始化堆 haffman.cpp:具体实现huffman算法

#pragma once

#include "stdafx.h"

template <class Type> class MinHeap{
public:
   MinHeap(int maxSize);//常成员函数不能修改this指向的内容
   MinHeap(Type arr[],int n);
   ~MinHeap(){delete[]heap;}
   int Insert(const Type &x);
   int RemoveMin(Type &x);//用参数作返回值
   Type DeleteMin();
   int IsEmpty()const{return CurrentSize==0;}
   int IsFull()const{return CurrentSize==MaxHeapSize;}
   void MakeEmpty(){CurrentSize=0;}
private:
   enum{DefaultSize=10};
   Type *heap;
   int CurrentSize;
   int MaxHeapSize;
   void FilterDown(const int start,const int end);
   void FilterUp(int start);
};
template <class Type> MinHeap<Type>::MinHeap(int maxSize){//根据给定大小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开始,到CurrentSize-1为止, 调整
       currentPos--;
   }
}
template <class Type> int MinHeap<Type>::Insert(const Type&x){//在堆中插入新元素x
   if(CurrentSize==MaxHeapSize){//堆满
       cout<<"堆已满"<<endl;
       return 0;
   }
   heap[CurrentSize]=x;//插在表尾
   FilterUp(CurrentSize);//向上调整为堆
   CurrentSize++;//堆元素增一
   return 1;
}
template <class Type> void MinHeap<Type>::FilterUp(int start){//从start开始,向上直到0,调整堆
   int j=start,i=(j-1)/2;//i是j的双亲
   Type temp=heap[j];
   while(j>0){
       if(heap[i].root->data.key<=temp.root->data.key)break;
       else{heap[j]=heap[i];j=i;i=(i-1)/2;}
   }
   heap[j]=temp;
}
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].root->data.key>heap[j+1].root->data.key)j++;
       if(temp.root->data.key<=heap[j].root->data.key)break;
       else{
           heap[i]=heap[j];
           i=j;
           j=2*j+1;
       }
   }
   heap[i]=temp;
}
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;
}
template <class Type> Type MinHeap<Type>::DeleteMin(){//不可以用引用，因为堆扩展时会覆盖返回的元素，引用会出错
   if(!CurrentSize){
       cout<<"Heap empty"<<endl;
       return 0;
   }
   Type x=heap[0];
   heap[0]=heap[CurrentSize-1];
   CurrentSize--;
   FilterDown(0,CurrentSize-1);
   return x;
}