堆排序的设计思想

堆排序中的数据的存储  采用树的顺序存储结构   理解树的顺序存储就要知道完全树  从而得出叶子结点和非叶子结点之间的关系
实现：（非递减的排序）
    1。从最后一个非叶子（p）结点开始  就从孩子当中挑选一个最大的与p结点进行比较 若是孩子大则不进行交换 改判断p前面的非叶子结点。
若是孩子结点小则进行交换。
    2。重复操作 1 直到所有的非叶子结点都操作完成
    3。完成上面两步 就完成了堆的建立（从无序序列到堆）
    4。把堆中的最后一个结点和最开始一个结点进行交换 从而原来堆的长度减少一，并且打破了堆的规则，所以要重新调整新堆 这时候只需要调整
第一个结点（堆顶）即可，其余的非叶子结点不用调整。（其中隐含的操作是当你调整第一个结点的时候 必定会相应的调整它的某个孩子结点的分支，
因为存在结点间的交换）
    5。完成4后堆中就是一个完全有序非递减的序列（下标的依次变化）得到相应的值.
#include <stdios.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct
{
    int length;/*堆的长度 零号下标不使用*/
    int *data;/*存储堆的数据*/
}Heap;
/*建立堆*/
int Create_Heap(Heap *h)
{
    int i = 0;
    printf("\tPrompt\nPlease input the size of the heap you want to create: ");
    scanf("%d", &i);
    printf("Input the datas: ");
    h->data = (int*) malloc (i*sizeof(int));
    h->length = 0;
    while( i-- )
    {
        ++h->length;
        scanf("%d", &h->data[h->length]);
    }
    return 0;
}
/*调整*/
int Adjust_Heap(Heap *h, int s, int m)
{
    int j = 0;
    h->data[0] = h->data[s];

    for( j=2*s; j<=m; j*=2 )
    {    /*如果有左右孩子 则左右孩子进行比较*/
        if( j<m && h->data[j] > h->data[j+1] )
        {/*如果左孩子大于右孩子 而且j<m 则进行下面的动作*/
            ++j;
        }
        if( !(h->data[0] > h->data[j]) )
        {/*如果双亲结点为最小 则后面的调整即可以不做 跳出for语句*/
            break;
        }
        h->data[s] = h->data[j];
        s = j;
    }
    h->data[s] = h->data[0];

    return 0;
}
/*排序*/
int Sort_Heap(Heap *h)
{
    int i = 0;
    for( i=h->length; i>0; --i )
    {/*由一个无序的序列 建成一个堆*/
        Adjust_Heap(h, i, h->length);
    }
    for( i=h->length; i>1; --i )
    {
        h->data[0] = h->data[1];
        h->data[1] = h->data[i];
        h->data[i] = h->data[0];

        Adjust_Heap(h, 1, i-1);
    }
    return 0;
}
/*输出*/
int Output_Heap(Heap *h)
{
    int i=0;
    for( i=1; i<=h->length; ++i )
    {
        printf("%d ", h->data[i] );
    }
    printf("\n");

    return 0;
}
int main()
{
    Heap *h = (Heap*) malloc (sizeof( Heap ));
    if( !h )
    {
        exit(0);
    }
    Create_Heap(h);
    Sort_Heap(h);
    Output_Heap(h);
    return 0;
}