creatheap.cpp

数据结构c++-书的一些源代码

void CreatHeap (elemtype x[], int n, int h)
/*对以x[h]为根结点的，x[h+1]--x[n-1]为根结点的二叉树已是堆的*/
/*二叉树建堆。堆顶元素为最大元素*/
{
   int i,j,flag;
   elemtype Temp;

   i=h;
   j=2*i+1;        /* j为i的左孩子的序号*/
   Temp=x[i];
   flag=0;

   /*沿左右孩子中值较大者重复向下筛选*/
   while(j<n && flag!=1)
   {
      /*寻找左右孩子中的较大者,j为其序号*/
      if(j<n-1 && x[j].key < x[j+1].key) j++;

      if(Temp.key > x[j].key)
        /*标记结束筛选条件*/
	 flag=1;
      else
      {
	/*当x[j] > x[i]时把x[j]上移*/
	 x[i]=x[j];

	 i=j;
	 j=2*i+1;
      }
   }
   /*把最初的x[i]赋予最后的x[j]*/
   x[i]=Temp;
}