heap.h

文件压缩与解压

# ifndef HEAP_CLASS
# define HEAP_CLASS

# include "ExtBinTree.h"

# include <iostream>
# include <vector>
using namespace std;

template <class T>
class Heap
{
public:
	Heap(){heap=NULL;}
	Heap(int MaxSize);
	void MakeHeap(vector<T>& fr);
	int Insert(const T& value);
	int RemoveMin(T& value);
	~Heap(){delete []heap;}
	void Destory(){delete []heap;}
	enum {DefaultSize=10000};
	void Show();
private:
	T* heap;
	int CurrentSize;
	int MaxHeapSize;
	void FilterDown(int i,int m);
	void FilterUp(int i);
};

template <class T>
Heap<T>::Heap(int MaxSize)
{
	MaxHeapSize=DefaultSize>MaxSize?DefaultSize:MaxSize;
	heap=new T[MaxHeapSize];
	CurrentSize=0;
}

template <class T>
void Heap<T>::FilterDown(int start, int end)
{
	int i=start,j=2*i+1;
	T temp1;
	while(j<=end)
	{
		if(j<end&&heap[j]>heap[j+1])
			j++;
		if(heap[i]<=heap[j])
			break;
		else
		{
			temp1=heap[i];
			heap[i]=heap[j];
			heap[j]=temp1;
			i=j;
			j=2*i+1;
		}
	}  
}

template <class T>
void Heap<T>::MakeHeap(vector<T>& fr)
{
	size_t n=fr.size();
	MaxHeapSize=n>DefaultSize?n:DefaultSize;
	heap=new T[MaxHeapSize];
	CurrentSize=n;
	for(size_t i=0;i<n;i++)
	{
		heap[i]=fr[i];
	}
	int CurrentPos=(CurrentSize-2)/2;
	while(CurrentPos>=0)
	{
		FilterDown(CurrentPos,CurrentSize-1);
		CurrentPos--;
	}
}

template <class T>
void Heap<T>::FilterUp(int start)
{
	int j=start,i=(j-1)/2;
	T temp1;
	while(j>0)
	{
		if(heap[i]<=heap[j])
			break;
		else
		{
			temp1=heap[i];
			heap[i]=heap[j];
			heap[j]=temp1;
			j=i;
			i=(j-1)/2;
		}
	}
}

template <class T>
int Heap<T>::Insert(const T& value)
{
	if(CurrentSize==MaxHeapSize)
	{
		cerr<<"The Heap is Full"<<endl;
		return 0;
	}
	heap[CurrentSize]=value;
	FilterUp(CurrentSize);
	CurrentSize++;
	return 1;
}

template <class T>
int Heap<T>::RemoveMin(T &value)
{
	if(!CurrentSize)
	{
		cout<<"Heap Empty"<<endl;
		return 0;
	}
	value=heap[0];
	heap[0]=heap[CurrentSize-1];
	CurrentSize--;
	FilterDown(0,CurrentSize-1);
	return 1;
}

# endif