heap_sort.c

heap_sort.c

// Hello world! Cplayground is an online sandbox that makes it easy to try out
// code.

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


void swap(int tree[],int i, int j){
    int tmp = tree[i];
    tree[i] = tree[j];
    tree[j] = tmp;
}


void heapfiy(int tree[], int n, int i){
    int lc = 2 * i + 1;
    int rc = 2 * i + 2;
    int max = i;
    if(lc<n && tree[lc]>tree[max]){
        max = lc;
    }
    if(rc<n && tree[rc]>tree[max]){
        max = rc;
    }
    if(max!=i){
        swap(tree, max, i);
        heapfiy(tree,n,max);
    }
}


void buildHeap(int tree[], int n){
    int lastNode = n-1;
    for(int i =(lastNode-1)/2 ;i>=0;i--){
        heapfiy(tree, n, i);
    }
}


void sort(int tree[], int n){
    for(int i = n-1;i>=0;i--){
        swap(tree,i,0);
        buildHeap(tree,i);
    }
}

int main() {
    int tree[] = {1,2,3,4,5,6,7,8};
    int n = 8;
    buildHeap(tree, n);
    printf("heapd\n");
    for(int i=0;i<n;i++){
        printf("%d\n",tree[i]);
    }
    printf("sorted\n");
    sort(tree, n);
    for(int i=0;i<n;i++){
        printf("%d\n",tree[i]);
    }
    return 0;
}