堆的算法.txt

常见算法

#include<iostream>
using namespace std;
int heapsize,length;                            //定义两个全局变量
void heapify(int a[],int i)                     //保持堆性质函数
{
int l,r,max,t;
l=2*i+1;                                        //计算以序号i为根的左子树序号　　　　　　　　　　　　　　　　　　　　　
r=2*i+2;                                        //计算以序号i为根的右子树序号
if(l<=heapsize && a[l]>a[i])
   max=l;
else
   max=i;
if(r<=heapsize && a[r]>a[max])
   max=r;
if(max!=i)
{t=a[i];a[i]=a[max];a[max]=t;heapify(a,max);}
}
void build_heap(int a[])                        //建堆函数
{
int i;
for(i=length/2-1;i>=0;i--)
   heapify(a,i);
}
void heapsort(int a[])                     //堆排序函数
{
int i,t;
build_heap(a);
for(i=0;i<length;i++)
   cout<<a[i]<<"  ";
cout<<endl;
for(i=length-1;i>=1;i--){
   t=a[0];a[0]=a[i];a[i]=t;
   heapsize--;
   heapify(a,0);}
}
void main()
{
int a[]={4,1,3,2,16,9,10,14,8,7},i;
length=sizeof(a)/sizeof(a[0]);
heapsize=sizeof(a)/sizeof(a[0])-1;
for(i=0;i<length;i++)
   cout<<a[i]<<"  ";
cout<<endl;
heapsort(a);
for(i=0;i<length;i++)
   cout<<a[i]<<"  ";
cout<<endl;
}