heap.cpp

常用算法代码

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


void swap(int &a, int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}


void shift_up(int a[], int i)
{
	bool done= false;
	if (i!=1)  {
		while(!done  && i!=1)  {
			if (a[i]>a[i/2]) 
			   swap(a[i],a[i/2]);
			else  done=1;
			i=i/2;
		}
	}
}


void shift_down( int a[], int n, int i)
{
	bool done=false;
	if ((2*i)<=n)  {
		while (!done&&((i=2*i)<=n))  {

			if (i+1<=n && a[i+1]>a[i])
				i=i+1;
			if (a[i/2]<a[i])
				swap(a[i/2],a[i]);
			else  done=1;
		}
	}
}



void insert(int a[], int & n, int x)
{
	n=n+1;
	a[n]=x;
	shift_up(a,n);
}

void del(int a[], int & n, int i)
{
	int x,y;
	x=a[i];
	y=a[n];
	n=n-1;
	if (i<=n)  {
		a[i]=y;
		if (y>=x)
			shift_up(a,i);
		else
			shift_down(a,n,i);
	}
}

void delete_max(int a[],int & n)
{
	del(a,n,1);
}

void make_heap1 (int a[], int n)
{
	int i;
	for (i=n/2;i>=1;i--)
		shift_down(a,n,i);
}

void make_heap2 (int a[],int n)
{
	int i,m=0;
	for (i=0;i<n;i++)
		insert(a,m,a[i]);
}

void heap_sort( int a[], int n)
{
	int i;
	make_heap1(a,n);
	for (i=n;i>1;i--)
	{
		swap(a[1],a[n]);
		shift_down(a,i-1,1);
	}
}


void print_array( int a[], int n)
{
	int i;
 	cout<<endl;
	for (i=1;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}



main()
{
	int a[12]={0,4,1,6,3,8,2,10,5,9,11,7};
	int i,m=0;
	print_array(a,12);
	heap_sort(a,12);
	print_array(a,12);
}