大神的世界

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIST_SIZE 10

void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp;}

void heapSort(int list[], int n);
void adjust(int list[], int root, int n);

int main()
{
    srand(time(NULL));
    int list[LIST_SIZE];

    list[0] = -1;
    for(int i = 1; i<LIST_SIZE; i++)
        list[i] = rand()%100;

    printf("before:\n");
    for(int i = 1; i<LIST_SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");

    heapSort(list, LIST_SIZE-1);

    return 0;
}

void heapSort(int list[], int n)
{
    for(int i = n/2; i>0; i--)
        adjust(list, i, n);

    printf("after:\n");
    // extract min to print
    for(int i = n-1; i>0; i--){
        printf("%d ", list[1]);
        swap(&list[1], &list[i+1]);
        adjust(list, 1, i);
    }
    printf("%d\n", list[1]);
}

void adjust(int list[], int root, int n)
{
    int value = list[root];
    int child = 2*root;

    while(child <= n){
        if(child < n && list[child] > list[child+1])
            child++;

        if(value < list[child])   // min heapify
            break;
        else{
            list[child/2] = list[child];
            child *= 2;
        }
    }

    list[child/2] = value;
}