heap.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>

#define DefaultSize 10

template <class Type>
class MinPQ
{
	public:
		virtual void Insert(const Type &)=0;
		virtual void Remove(Type &)=0;
};
template <class Type>
class MinHeap:public MinPQ<Type>
{
	public:
		MinHeap(int sz);
		MinHeap(){};
		MinHeap(Type arr[],int n);
		MinHeap(const MinHeap &r);
		~MinHeap(){delete []heap;}
		bool Insert(const Type &x);//插入
		bool Remove(Type &x);		//删除
		bool IsEmpty()const {return currentSize==0;}
		bool IsFull()const {return currentSize==maxSize;}
		void MakeEmpty(){currentSize=0;}
	private:
		Type *heap;
		int currentSize;
		int maxSize;
		void FilterDown(int i,int m);//从i到m自顶向下进行调整成为最小堆
		void FilterUp(int i);		//从到自底向上进行调整成为最小堆
};
template <class Type>
MinHeap<Type>::MinHeap(int sz)
{
	maxSize=sz;
	currentsize=0;
	heap=new Type[sz];
	if(heap==NULL)
	{
		cerr<<"the memory is not enough";
		exit(1);
	}
}

template <class Type>
MinHeap<Type>::MinHeap(Type arr[],int n)
{
	currentsize=n;
	maxSize=2*n;
	heap=new Type[maxSize];
	for(int i=0;i<n;i++)
		heap[i]=arr[i];
	int currentPos=(currentSize-2)/2;//找最初调整位置；最后的分支结点号
	while(currentPos>=0)			//从下到上一个一个扩大，形成堆
	{
		FilerDown(currentPos,currentSize-1);//从currentPos开始，到止currentSize，调整
		currentPos-1;
	}
}

template <class Type>
void MinHeap<Type>::FilterDown(int start,int EndOfHeap)//对有M个记录的集合R，将它置为完全二叉树的顺序存贮
{														//
	int i=start,j=2*i+1;	//j是i的左子女
	Type tmep=heap[i];
	while(j<=EndOfHeap)
	{
		if(j<EndOfHeap&&heap[j]>heap[j+1])j++;//两个子女选择小的
		if(temp<=heap[j])break;
		else
		{
			heap[i]=heap[j];		//下面的上浮
			i=j;j=2*j+1;			//向下动
		}
	}
	heap[i]=temp;
}

template <class Type>
bool MinHeap<Type>::Insert(const Type &x)
{
	if(IsFull())
	{
		cerr<<"the heap is full";
		return false;
	}
	heap[currentSize]=x;
	FilterUp(currentSize);
	currentSize++;
	return true;
}

template <class Type>
void MinHeap<Type>::FilterUp(int start)
{
	int j=start,i=(j-1)/2;		//i是j的双亲
	Type temp=heap[j];
	while(j>0)					//沿双亲结点路线向上直达根结点
	{
		if(heap[i]<=tmep)break;//双亲结点值小，不调整
		else
		{
			heap[j]=heap[i];	//双亲结点值大，调整
			j=i;i=(j-1)/2;
		}
	}
	heap[j]=temp;			//回送
}

template <class Type>
bool MinHeap<Type>::Remove(Type &x)
{
	if(currentSize==0)
	{
		cerr<<"the heap is empty";
		return false;
	}
	x=heap[0];
	heap[0]=heap[currentSize-1];
	currentSize--;
	FilterDown(0,cuurentSize-1);
	return true;
}