heapsort_tree.c

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

typedef struct node_t node_t;

struct node_t {
    int val;
    node_t *parent;
    node_t *left;
    node_t *right;
};

typedef struct heap_t heap_t;

struct heap_t {
    node_t *root;
    node_t *leaf;
    node_t *pool;
    int pool_idx;
};

node_t *heap_create_node(heap_t *heap) {
    node_t *node = &heap->pool[heap->pool_idx++];
    node->val = 0;
    node->parent = node->left = node->right = 0;
    return node;
}

void node_free(node_t *node) {
    // nothing to do here
}

void push_down(node_t *node) {
    if (!node)
        return;
    node_t *max;
    if (node->left && node->left->val > node->val)
        max = node->left;
    else
        max = node;
    if (node->right && node->right->val > max->val)
        max = node->right;
    if (max != node) {
        int t = node->val;
        node->val = max->val;
        max->val = t;
        push_down(max);
    }
}

node_t *heap_build(heap_t *heap, int *arr, int offset, int size) {
    if (size <= 0)
        return 0;
    int right_size = (size - 1) / 2;
    int left_size = size - 1 - right_size;
    node_t *root = heap_create_node(heap);
    root->val = arr[offset];
    root->left = heap_build(heap, arr, offset + 1, left_size);
    if (root->left)
        root->left->parent = root;
    root->right = heap_build(heap, arr, offset + left_size + 1, right_size);
    if (root->right)
        root->right->parent = root;
    push_down(root);
    return root;
}

node_t *find_leaf(node_t *node) {
    if (!node)
        return 0;
    node_t *leaf = node;
    while (leaf->left || leaf->right) {
        while (leaf->left)
            leaf = leaf->left;
        while (leaf->right)
            leaf = leaf->right;
    }
    return leaf;
}

heap_t *heap_new(int *arr, int size) {
    heap_t *heap = (heap_t*)malloc(sizeof(heap_t));
    heap->pool = (node_t*)malloc(sizeof(node_t) * size);
    heap->pool_idx = 0;
    heap->root = heap_build(heap, arr, 0, size);
    heap->leaf = find_leaf(heap->root);
    return heap;
}

void heap_free(heap_t *heap) {
    if (!heap)
        return;
    node_free(heap->root);
    free(heap->pool);
    free(heap);
}

int heap_extract_max(heap_t *heap) {
    assert(heap && heap->root);
    int max = heap->root->val;
    heap->root->val = heap->leaf->val;
    node_t *leaf_parent = heap->leaf->parent;
    if (leaf_parent) {
        if (leaf_parent->left == heap->leaf)
            leaf_parent->left = 0;
        else if (leaf_parent->right == heap->leaf)
            leaf_parent->right = 0;
        node_free(heap->leaf);
    } else {
        node_free(heap->root);
        heap->root = 0;
    }
    heap->leaf = find_leaf(leaf_parent);
    push_down(heap->root);
    return max;
}

void sort(int *arr, int size) {
    heap_t *heap = heap_new(arr, size);
    for (int i = size-1; i >= 0; i--) {
        arr[i] = heap_extract_max(heap);
    }
    heap_free(heap);
}

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;
}