heap.h

二叉树

//堆定义   最小堆

#ifndef HEAP
#define HEAP

#include<iostream.h>

const int size=20;
template<class T>
class MinHeap{
public:
	MinHeap();
	void makeMinTree(T data[],int len);
	void makeMinTree_modify(T data[],int len);
	void insertHeapNode(T el);
	void deleteHeapNode();
	void PrintAll();
private:
	T minHeap[size];
};

template<class T>
MinHeap<T>::MinHeap()
{
	for(int i=1;i<=size;i++)   //堆是下标从1开始的
	{
		minHeap[i]=-1;
	}
}
template<class T>
void MinHeap<T>::makeMinTree(T data[],int len)  //从空堆开始建堆
{
	int i;
	for(i=0;i<len;i++)
	{
		insertHeapNode(data[i]);
	}
}
template<class T>
void MinHeap<T>::makeMinTree_modify(T data[],int len)  //从数组建堆，通过调整实现
{
	int i;
	for(i=0;i<len;i++)
	{
		minHeap[i+1]=data[i];
	}
	i=i/2;
	while(i!=1)
	{
		if(len%2==0)
		{
		    if(minHeap[2*i]<minHeap[i])
			{
			    tmp=minHeap[2*i];
			    minHeap[2*i]=minHeap[i];
		    	minHeap[i]=tmp;
			    i--;
			}
			int j=2*i;
			while()
		}
		else
		{
			if(minHeap[i]>minHeap[2*i]&&minHeap[i]>minHeap[2*i+1])
			{
				if(minHeap[2*i]<minHeap[2*i+1])
				{
			        tmp=minHeap[2*i];
			        minHeap[2*i]=minHeap[i];
		    	    minHeap[i]=tmp;
			        i--;
				}
				else
				{
			        tmp=minHeap[2*i+1];
			        minHeap[2*i+1]=minHeap[i];
		    	    minHeap[i]=tmp;
			        i--;
				}
			}
			while()
		}
	}
}
template<class T>
void MinHeap<T>::insertHeapNode(T el)
{
	int i,tmp;
	for(i=1;i<size;i++)
	{
		if(minHeap[i]==-1)
		{
			minHeap[i]=el;    //找到最后一个结点，插入
			break;
		}
	}
	while(minHeap[i/2]>minHeap[i])  //调整
	{
		tmp=minHeap[i];
		minHeap[i]=minHeap[i/2];
		minHeap[i/2]=tmp;
		i=i/2;
	}
}

template<class T>
void MinHeap<T>::deleteHeapNode()           //从根节点删除
{
	int i;
	T tmp;
	for(i=1;i<=size;i++)
	{
		if(minHeap[i]==-1)
			break;
	}
	tmp=minHeap[i-1];
	minHeap[i-1]=-1;
	i=1;
	minHeap[i]=tmp;
	while(minHeap[i]!=-1)
	{
		if(minHeap[2*i]!=-1&&minHeap[2*i+1]!=-1&&minHeap[i]>minHeap[2*i]&&minHeap[i]>minHeap[2*i+1])
		{
		    if(minHeap[2*i]<minHeap[2*i+1])  //左孩子更小，和左孩子换
			{
			    tmp=minHeap[i];    
			    minHeap[i]=minHeap[2*i];
			    minHeap[2*i+1]=tmp;
			    i=2*i;
			}
		    else
			{
			    tmp=minHeap[i];
			    minHeap[i]=minHeap[2*i+1];
		    	minHeap[2*i+1]=tmp;
			    i=2*i+1;
			}
		}
		else
		{
			if(minHeap[2*i]!=-1&&minHeap[i]>minHeap[2*i])          //只比左孩子大，和左孩子换
			{
				tmp=minHeap[i];
				minHeap[i]=minHeap[2*i];
				minHeap[2*i]=tmp;
			}
			else if(minHeap[2*i+1]!=-1&&minHeap[i]>minHeap[2*i+1]) //只比右孩子大，和右孩子换
			{
				tmp=minHeap[i];
				minHeap[i]=minHeap[2*i+2];
				minHeap[2*i+2]=tmp;
			}
			else
				break;  //正好，跳出
		}
	}
}
template<class T>
void MinHeap<T>::PrintAll()
{
	for(int i=1;i<size;i++)
	{
		if(minHeap[i]!=-1)
			cout<<minHeap[i]<<' ';
		else
			break;
	}
	cout<<endl;
}
#endif