heapsort.c

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

int left(int i) {
    return 2 * i;
}

int right(int i) {
    return 2 * i + 1;
}

void down(int *arr, int size, int i) {
    int l = left(i);
    int r = right(i);
    int max;
    if (l < size && arr[l] > arr[i])
        max = l;
    else
        max = i;
    if (r < size && arr[r] > arr[max])
        max = r;
    if (max != i) {
        int t = arr[i];
        arr[i] = arr[max];
        arr[max] = t;
        down(arr, size, max);
    }
}

void make_heap(int *arr, int size) {
    for (int i = size/2; i >= 0; i--) {
        down(arr, size, i);
    }
}

void sort(int *arr, int size) {
    make_heap(arr, size);
    while (--size) {
        int t = arr[0];
        arr[0] = arr[size];
        arr[size] = t;
        down(arr, size, 0);
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    assert(n > 0);

    int *arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", arr + i);

    sort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    free(arr);
    return 0;
}