힙정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int *makelist(int max, int n) {

    int *al=(int*)calloc(n,sizeof(int));

    int i;

    srand(time(NULL));

    for(i=0;i<n;i+=1) {

        al[i]=rand()%max+1;

    }

    return al;

}

void downheap(int h[], int i, int n) {

    int v, ix, temp;

    v=h[i];

    while(i<n/2) {

        ix=i+i+1;

        if(ix<n-1 && h[ix]<h[ix+1]) {

            ix+=1;

        }

        if(v>h[ix]) { break; }

        h[i]=h[ix];

        i=ix;

    }

    h[i]=v;

}

void upheap(int h[], int i, int v) {

    int ip=(i-1)/2;

    h[i]=v;

    while(i>0 && v>h[ip]) {

        h[i]=h[ip];

        i=ip;

        ip=(ip-1)/2;

    }

    h[i]=v;

}

void heapify(int h[], int n) {

    int i=n/2-1;

    while(i>=0) {

        downheap(h, i, n);

        i-=1;

    }

}

void heapsort(int h[], int n) {

    int x, temp;

    heapify(h, n);

    for(x=n-1;x>0;x-=1) {

        temp=h[0]; h[0]=h[x]; h[x]=temp;

        downheap(h, 0, x);

    }

}

void printheap(int h[], int n) {

    int i;

    for(i=0;i<n;i+=1) {

        printf("%3d ", h[i]);

    }

    printf("\n");

}

int main() {

    int *heap;

    int n;

    printf("정수: ");

    scanf("%d", &n);

    heap=makelist(1000, n);

    printf("** before **\n");

    printheap(heap, n);

    heapsort(heap, n);

    printf("** after **\n");

    printheap(heap, n);

    free(heap);

    return 0;

}