minheap.cpp

堆的实现

#include"MinHeap.h"
void MinHeapAdjust(MinHeap &h)
{
	int i,j;
	ElemType item;
	item=h.h[1];
	for(i=2;j<=h.curlength ;j*=2)
	{
		if(j<m&&(h.h[j]>h.h[j+1])++j;
		if(!(item<h.h[j])break;
		h.h[1]=h.h[j];
		s=j;
	}
	h.h[s]=item;
}
void MinHeapSort(MinHeap &h)
{
	int i;
	ElemType temp;
	for(i=h.curlength /2;i>0;--i)
		MinHeapAdjust(h);
	for(i=h.curlength ;i>1;--i)
	{temp=h.h[1];
	h.h[1]=h.h[i];
	h.h[i]=temp;
	MinHeapAdjust(h);
	}
}

bool InitilizeMinHeap(MinHeap &h)
{
	if(h.h=(ElemType*)malloc(MAX_ELEMENTS*sizeof(ElemType)))
		{
			h.curlength =0;
			h.maxsize =MAX_ELEMENTS-1;
			return true;
		}
	else
		return false;
}

void InsertMinHeap(MinHeap &h,ElemType item)
{
	int i;
	if(h.curlength ==MAX_ELEMENTS-1)
	{
		cout<<"The Min Heap is full."<<endl;
		exit(1);
	}
	i=++h.curlength ;
	while((i!=1)&&(item<h.h[i/2]))
	{
		h.h[i]=h.h[i/2];
		i/=2;
	}
	h.h [i]=item;
}

ElemType DeleteMinHeap(MinHeap &h)
{
	int parent,child;
	ElemType temp,item;
	if(h.curlength ==0)
	{
		cout<<"The Max Heap is empty."<<endl;
		exit(1);
	}
	item=h.h[1];
	temp=h.h[h.curlength --];
	parent=1;
	child=2;
	while(child<=h.curlength )
	{
		if(temp<h.h[child])
			break;

		h.h[parent]=h.h[child];
		parent=child;
		child*=2;
	}

	
	h.h [parent]=temp;
	return item;
}