#include
#include
using namespace std;

void HeapAdjust(int *a,int i,int size)  //调整堆
{
   int lchild = 2*i;       //i的左孩子节点序号
   int rchild = 2*i+1;     //i的右孩子节点序号
   int max = i;            //临时变量
   if(i <= size/2)          //如果i是叶节点就不用进行调整
   {
        if(lchild <= size && a[lchild]>a[max])
        {
            max=lchild;
        }    
        if(rchild <= size&& a[rchild] > a[max])
        {
            max=rchild;
        }
        if(max!=i)
        {
            swap(a[i], a[max]);
            HeapAdjust(a, max, size);    //避免调整之后以max为父节点的子树不是堆
        }
    }        
}

void BuildHeap(int *a,int size)    //建立堆
{
    inti;
    for(i=size/2; i>=1; i--)    //非叶节点最大序号值为size/2 
    {
        HeapAdjust(a,i,size);    
    }    
} 

void HeapSort(int *a,int size)    //堆排序
{
    int i;
    BuildHeap(a,size);//建立最大堆
    for(i=size; i>=1; i--)
    {
        //cout<0)
     {
         int i;
         for(i=1;i<=size;i++)
             cin>>a[i];
         HeapSort(a,size);
         for(i=1;i<=size;i++)
             cout<        

标签: none

添加新评论