heap.c

heap.c

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

typedef struct {
    size_t size;
    size_t capacity;
    void **elements;

    char (*compare)(const void *, const void *);
} heap_t;

heap_t *heap_create(char (*compare)(const void *, const void *)) {
    heap_t *res = malloc(sizeof(heap_t));
    res->size = 0;
    res->capacity = 1;
    res->elements = malloc(sizeof(void *));
    res->compare = compare;
    return res;
}

void *heap_top(heap_t *heap) {
    return *(heap->elements);
}

void heap_push(heap_t *heap, void *element) {
    // check capacity
    if (heap->size >= heap->capacity) {
        // resize to 2*capacity
        const size_t new_cap = heap->capacity * 2 + 1;
        heap->elements = realloc(heap->elements, new_cap * sizeof(void *));
        // TODO: solve failed memory allocate
        heap->capacity = new_cap;
    }
    // push
    size_t ptr = heap->size;
    heap->elements[heap->size++] = element;
    // heapify
    while (ptr > 0) {
        const size_t father = (ptr - 1) / 2;
        if (heap->compare(element, heap->elements[father])) {
            // swap
            heap->elements[ptr] = heap->elements[father];
            heap->elements[father] = element;
        } else {
            break;
        }
        ptr = father;
    }
}

void heap_pop(heap_t *heap) {
    if (heap->size == 0) {
        // empty, do nothing
        return;
    }
    // move the last one to the top
    heap->size -= 1;
    heap->elements[0] = heap->elements[heap->size];
    // heapify
    size_t ptr = 0;
    while (ptr < heap->size) {
        const size_t left_ptr = ptr * 2 + 1;
        const size_t right_ptr = ptr * 2 + 2;
        if (left_ptr >= heap->size) {
            // no child
            break;
        }
        void *left_child = heap->elements[left_ptr];
        if (right_ptr >= heap->size) {
            // no right child
            if (heap->compare(left_child, heap->elements[ptr])) {
                // swap left child
                void *tmp = heap->elements[ptr];
                heap->elements[ptr] = left_child;
                heap->elements[left_ptr] = tmp;
            }
            break;
        }
        void *right_child = heap->elements[right_ptr];
        if (heap->compare(heap->elements[ptr], left_child) && heap->compare(heap->elements[ptr], right_child)) {
            break;
        }
        if (heap->compare(left_child, right_child)) {
            // swap left child
            void *tmp = heap->elements[ptr];
            heap->elements[ptr] = left_child;
            heap->elements[left_ptr] = tmp;
            ptr = left_ptr;
        } else {
            // swap right child
            void *tmp = heap->elements[ptr];
            heap->elements[ptr] = right_child;
            heap->elements[right_ptr] = tmp;
            ptr = right_ptr;
        }
    }
    // shrink size
    if (heap->size < heap->capacity / 2) {
        const size_t new_cap = heap->capacity / 2;
        heap->elements = realloc(heap->elements, new_cap * sizeof(void *));
        heap->capacity = new_cap;
    }
}

char heap_is_empty(heap_t *heap) {
    return heap->size == 0 ? 1 : 0;
}

#define TEST_RANDOM 1

char less(const void *a, const void *b) {
    return (*(int *) a) < (*(int *) b) ? 1 : 0;
}

int main() {
    heap_t *h = heap_create(less);
#if TEST_RANDOM
    // generate random test data
    srand((unsigned) time(NULL));
    const int n = 10000;
    int arr[n];
    arr[0] = 0;
    for (int i = 1; i < n; i++) {
        arr[i] = rand() % 10 + arr[i - 1];
    }
    // print origin array
    puts("Origin Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    // shuffle ptr
    puts("\nShuffled array: ");
    int *arr_ptr[n];
    for (int i = 0; i < n; i++) {
        arr_ptr[i] = &arr[i];
    }
    for (int i = 0; i < n; i++) {
        int t = rand() % (n - i);
        // swap
        int *tmp = arr_ptr[i];
        arr_ptr[i] = arr_ptr[i + t];
        arr_ptr[i + t] = tmp;
        printf("%d ", *arr_ptr[i]);
    }
    // heap sort
    puts("\nHeap sorted: ");
    for (int i = 0; i < n; i++) {
        heap_push(h, arr_ptr[i]);
    }
    // pop and check
    char is_same = 1;
    for (int i = 0; i < n; i++) {
        int top = *(int *) heap_top(h);
        heap_pop(h);
        if (top != arr[i]) {
            printf("\nWrong number in index %d, got %d, expected %d\n", i, top, arr[i]);
            is_same = 0;
        } else {
            printf("%d ", top);
        }
    }
    if (is_same) {
        puts("\nHeap works fine.");
    } else {
        puts("\nHeap not good.");
    }
#else
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
        heap_push(h, arr + i);
    }
    while (h->size) {
        printf("%d ", *(int *) heap_top(h));
        heap_pop(h);
    }
#endif
    return 0;
}