[ create a new paste ] login | about

Link: http://codepad.org/MN7XiyCJ    [ raw code | output | fork ]

johannes - C, pasted on Mar 9:
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

#ifndef BOOL
#define BOOL int
#endif

#define HEAP_DATATYPE int

typedef struct heapstruct heapstruct;

struct heapstruct
{
    size_t capacity;
    size_t size;
    HEAP_DATATYPE *data;
};

static void
heap_grow(heapstruct *heap)
{
    assert(heap);
    heap->capacity += heap->capacity;
    heap->data = realloc(heap->data, heap->capacity * sizeof(HEAP_DATATYPE));
}

heapstruct *
heap_new(const size_t size)
{
    heapstruct *h;
    h = malloc(sizeof(heapstruct));
    if (h) {
        h->data = malloc(size * sizeof(HEAP_DATATYPE));
        if (!h->data) {
            free(h);
            return NULL;
        }
        h->size = 0;
        h->capacity = size;
    }
    return h;
}

void
heap_destroy(heapstruct *heap)
{
    if (!heap)
        return;
    free(heap->data);
    free(heap);
}

BOOL
heap_is_empty(heapstruct *heap)
{
    assert(heap);
    return 0 == heap->size;
}

BOOL
heap_is_full(heapstruct *heap)
{
    assert(heap);
    return heap->size == heap->capacity;
}

void
heap_insert(heapstruct *heap, HEAP_DATATYPE element)
{
    int i;
    if (heap_is_full(heap))
        heap_grow(heap);
    i = heap->size;
    while (i && heap->data[i / 2] > element) {
        heap->data[i] = heap->data[i / 2];
        i /= 2;
    }
    heap->data[i] = element;
    ++heap->size;
}

HEAP_DATATYPE
heap_extract_min(heapstruct *heap)
{
    unsigned int i, c;
    HEAP_DATATYPE first, last;
    if (heap_is_empty(heap))
        return 0;

    first = heap->data[0];
    last = heap->data[--heap->size];

    i = 0;
    while (i+i <= heap->size + 1) {
        c = i ? i + i : 1;
        if (c != heap->size && heap->data[c + 1] < heap->data[c])
            ++c;
        if (last > heap->data[c])
            heap->data[i] = heap->data[c];
        else
            break;
        i = c;
    }
    heap->data[i] = last;

    return first;
}

int 
main(void)
{
    int x;
    heapstruct *h;

    h = heap_new(32);

    heap_insert(h, 32);
    heap_insert(h, 5);
    heap_insert(h, 1);
    heap_insert(h, 15);
    heap_insert(h, 7);
    heap_insert(h, 2);

    x = heap_extract_min(h);
    printf("x = %d\n", x);
    x = heap_extract_min(h);
    printf("x = %d\n", x);
    x = heap_extract_min(h);
    printf("x = %d\n", x);
    x = heap_extract_min(h);
    printf("x = %d\n", x);
    x = heap_extract_min(h);
    printf("x = %d\n", x);
    x = heap_extract_min(h);
    printf("x = %d\n", x);

    heap_destroy(h);
    return 0;
}


Output:
1
2
3
4
5
6
x = 1
x = 2
x = 5
x = 7
x = 15
x = 32


Create a new paste based on this one


Comments: