ヒープのソート--小根ヒープの作成と調整

#include
#include
typedef int ElemType;
struct HeapSq //          
{
    ElemType* heap; //             
    int len; //          ,     ，     0  
    int MaxSize;    //                    
};

//1、    
void InitHeap(struct HeapSq* HBT, int MS)
{
    if (MS <= 0)
    {
        printf("         ，     ！
");
        exit(1);
    }
    HBT->heap = malloc(MS*sizeof(ElemType));
    if (!HBT->heap)
    {
        printf("             ，    ！
");
        exit(1);
    }
    HBT->MaxSize = MS;
    HBT->len = 0;
}

//2、   
void ClearHeap(struct HeapSq* HBT)
{
    if (HBT->heap != NULL)
    {
        free(HBT->heap);
        HBT->len = 0;
        HBT->MaxSize = 0;
    }
}

//3、         
int EmptyHeap(struct HeapSq* HBT)
{
    if (HBT->len == 0)
        return 1;
    else
        return 0;
}

//4、         
void InsertHeap(struct HeapSq* HBT, ElemType x)
{
    int i;
    if (HBT->len == HBT->MaxSize) //   ，           2 
    {
        ElemType *p;
        p = realloc(HBT->heap, 2*HBT->MaxSize*sizeof(ElemType));
        if (!p)
        {
            printf("      ！
");
            exit(1);
        }
        printf("           2 ！
");
        HBT->heap = p;
        HBT->MaxSize = 2*HBT->MaxSize;
    }
    HBT->heap[HBT->len] = x; //        
    HBT->len++; //    1
    i = HBT->len - 1; //i          ，      ，              
    while (i != 0)
    {
        int j = (i - 1) / 2; //j     i      
        if (x >= HBT->heap[j]) //              ，       ，    
            break;
        HBT->heap[i] = HBT->heap[j]; //                
        i = j; //             ，       
    }
    HBT->heap[i] = x;//           
}

//5、            
ElemType DeleteHeap(struct HeapSq* HBT)
{
    ElemType temp, x;
    int i, j;
    if (HBT->len == 0)
    {
        printf("   ，    ！
");
        exit(1);
    }
    temp = HBT->heap[0]; //      
    HBT->len--;
    if (HBT->len == 0) //            
        return temp;
    x = HBT->heap[HBT->len]; //            x ，        
    i = 0; // i          ，        
    j = 2 * i + 1;// j  i      ，       1   
    while (j <= HBT->len - 1)//            ，           ，         
    {
        if (j < HBT->len - 1 && HBT->heap[j] > HBT->heap[j+1])//         ， j     
            j++;
        if (x <= HBT->heap[j]) // x         ，     ，    
            break;
        HBT->heap[i] = HBT->heap[j];//  ，           
        i = j; //                
        j = 2 * i + 1;// j               ，       
    }
    HBT->heap[i] = x; // x      
    return temp; //       
}

//   
void main()
{
    int i, x;
    int a[8] = {23,56,40,62,38,55,10,16};
    struct HeapSq b;
    InitHeap(&b, 10);
    for (i = 0; i < 8; i++)
        InsertHeap(&b, a[i]);
    while (!EmptyHeap(&b)) //             ，      
    {
        x = DeleteHeap(&b);
        printf("%d", x);
        if (!EmptyHeap(&b))
            printf(",");
    }
    printf("
");
    system("pause");
    ClearHeap(&b);
}