heapsort.c

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


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

static inline int left(int i) { return i * 2 + 1; }
static inline int right(int i) { return left(i) + 1; }
static inline int parent(int i) { return (i - 1) / 2; }

static void percolate_up(int *nums, int i)
{
        while (i > 0 && nums[parent(i)] < nums[i]) {
                swap(nums + parent(i), nums + i);
                i = parent(i);
        }
}

static void percolate_down(int *nums, int size)
{
        int i, max;
        for (i = 0; i < size / 2; i = max) {
                if (right(i) < size) {
                        max = nums[left(i)] > nums[right(i)] ? left(i) : right(i);
                } else {
                        max = left(i);
                }
                if (nums[i] < nums[max]) {
                        swap(nums + i, nums + max);
                }
        }
}

static void heap_sort(int *nums, int size)
{
        int i;
        for (i = 0; i < size; i++) {
                percolate_up(nums, i);
        }

        while (size-- > 0) {
                swap(nums, nums + size);
                percolate_down(nums, size);
        }
}

int main(int argc, char **argv)
{
        int i, count = argc - 1;
        int *nums = malloc(count * sizeof(int));

        for (i = 0; i < count; i++) {
                nums[i] = atoi(argv[i+1]);
        }
        
        heap_sort(nums, count);
        
        for (i = 0; i < count; i++) {
                printf("%d ", nums[i]);
        }
        printf("\n");

        return 0;
}