堆的建立.txt

数值方法课程中的程序

程序：堆的建立，由一个空堆，不断进行插入函数的调用，生成一个新堆。需要注意的是，插入第一个数时，与0进行比较，所以这个0不会消失，需要最后对其进行删除操作，因此在建立堆的过程中，要随时记录这个0的具体位置，以便最后进行删除。本程序中子函数包括上移、下移、插入、建立以及删除函数。完全实现预期的功能。
#include<iostream.h>
int N=1;
void sift_up(int H[],int i)
{  int t;
   bool done=false;
   if(i!=0)
   {  while(!done && i!=0)

      {  if(H[i]>H[(i-1)/2])
           {  t=H[i];H[i]=H[(i-1)/2];H[(i-1)/2]=t;
              
              if(((i-1)/2)==N)
              {N=i;}
            }
         else done=true;
         i=(i-1)/2;
      }
   }
}

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

      {  if((i+2)<=n && H[i+2]>H[i+1])
           i=i+2;
         else i=i+1;
         if(H[(i-1)/2]<H[i])
           {  t=H[(i-1)/2];H[(i-1)/2]=H[i];H[i]=t;}
         else done=true;
      }
   }
}

void insert(int H[],int n,int x)
{  n=n+1;
   H[n]=x;
   sift_up(H,n);
}

void make_heap1(int A[],int H[],int n)
{  int i,m=0;
   for(i=0;i<n;i++)
     {insert(H,m,A[i]);
       m=m+1;}
}

void delete1(int H[],int n,int i)
{  int x,y;
   x=H[i];
   y=H[n];
   n=n-1;
   if(i<=n)
   {  H[i]=y;
      if(y>=x)
        sift_up(H,i);
      else
        sift_down(H,n,i);
   }
}

void main()
{  int k;
   int a[]={25,1,3,17,23,12,29,33,11,7,15,78,35,68,356,796,235,678,34,79};
   int b[20]={};
   make_heap1(a,b,20);
   for(k=0;k<=20;k++)
   cout<<b[k]<<endl;
   delete1(b,20,N);
   for(k=0;k<20;k++)
   {cout<<b[k]<<endl;}
   cout<<N;
   
 }