priority_queues.c

是个HEAP SORT 算法..对一个数列进行HEAP SORT

#include <iostream.h>
#include <iomanip.h>
#define Max 10000


void HeapUp(int **S,int i)
{
	bool done=false; 
	int temp;
	if(i!=1)
	{
		while(!done&&i!=1)
		{
			if((*S)[i]>(*S)[i/2])
			{
				temp=(*S)[i];
				(*S)[i]=(*S)[i/2];
				(*S)[i/2]=temp;
			}
			else done=true;
			i=i/2;
		}
	}
}

void HeapDown(int **S,int i)
{
	bool done=false;
	int n,temp;
	n=(*S)[0];
	if(2*i<=1)
	{
		while(!done&&(i=2*i)<=n)
		{
			if(i+1<=n&&(*S)[i+1]>(*S)[i])
				i=i+1;
			if((*S)[i/2]<(*S)[i])
			{
				temp=(*S)[i/2];
				(*S)[i/2]=(*S)[i];
				(*S)[i]=temp;
			}
			else done=true;
		}
	}
}

void Print(int *S)
{
	int i,n;
	n=S[0];
	for(i=1;i<=n;i++)
		cout<<setw(3)<<S[i];
	cout<<endl;
	
}


void Insert(int **S,int key)
{
	int i;
	i=(*S)[0];
	(*S)[i+1]=key;
	((*S)[0])++;
	HeapUp(S,(*S)[0]);
}

int  Maxmum(int *S)
{
		cout<<"The maxmum number is:"<<S[1]<<endl;
		return S[1];
}

int ExtractMax(int **S)
{
	int i,max;
	i=(*S)[0];
	if(i=0)
		cout<<"Heap underflow!!";
	max=(*S)[1];
	(*S)[1]=(*S)[i];
	i--;
	HeapUp(S,i);
	return max;
}

void OverwriteKey(int **S,int i, int key)
{
	if(key<(*S)[i])
	{
		cout<<"New key is smaller then the current key!!!\n";
	}
	(*S)[i]=key;
	HeapUp(S,i);
}

void Initial(int **S)
{
	*S=new int[Max];
	(*S)[0]=NULL;
}

void main()
{
	int i,n;
	int key,*S;
	Initial(&S);
		cout<<"The total number of the inserting elements:";
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>key;
			Insert(&S,key);
		}
		
	cout<<"After overwrite ,the arry becomes :\n";
	Print(S);
	n=Maxmum(S);
	cout<<"Which element do you want to change?\n";
	cin>>i;
	cout<<"Change into :";
	cin>>key;
	OverwriteKey(&S,i,key);
	cout<<"After change ,the arry becomes :\n";
	Print(S);
}