算法2.13--改进的堆修复过程(AfixHeap)

ＢＴＷ：发现自己智商有问题地说...

还是觉得原书的算法描述对某些输入还是有问题地说...-_-b

 

#include
#include
#include

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{
        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
        {
                printf("%d      ", list[i]);
        }

        printf("\n");
}

/*algorithm*/
void a_fix_heap(int * list, int h_size, int vac, int k)
{
        int this_vac = vac;
        while((2*vac +1) < h_size)
        {
                if(list[2*vac +1] < list[2*vac +2])
                {
                        list[vac] = list[2*vac +2];
                        vac = 2*vac +2;
                }
                else
                {
                        list[vac] = list[2*vac +1];
                        vac = 2*vac +1;
                }
        }

        if((2*vac +1) == h_size) /*If vacation is moved to a node with one leaf*/
        {
                if(list[2*vac+1] > k)
                {
                        list[vac] = list[2*vac+1];
                        vac = 2*vac+1;
                }

        }

        while(k > list[(vac-1)/2] && (vac-1)/2 >= this_vac)
        {
                list[vac] = list[(vac-1)/2];
                vac = (vac-1)/2;
                if(vac == 0)
                {
                        break;
                }
        }

        list[vac] = k;
        return;
}

void build_heap(int * list, int length)
{
        int i;
        for(i = (length+1)/2; i >= 0; i --)
        {
                a_fix_heap(list, length, i, list[i]);
        }
        return;
}

void heap_sort(int * list, int length)
{
        int i;
        build_heap(list, length - 1);
        for(i = length -1; i >= 1; i --)
        {
                int temp = list[i];
                list[i] = list[0];
                a_fix_heap(list, i -1, 0, temp);
        }
}

int main(int argc, char * argv[])
{
        int length;
        int * list = NULL;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                printf("Soruce list:\n");
                show_list(list, length);

                heap_sort(list, length);

                printf("Ordered list:\n");
                show_list(list, length);
        }

        free(list);
        return 1;
}