heap.c

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

typedef struct {
    int* tab;
    int nb;
} heap_t;

heap_t* heap_create(size_t n);
void    heap_insert(heap_t* h, int v);
int     heap_getAndRemoveMin(heap_t* h);
int     heap_getMin(heap_t* h);
void    heap_free(heap_t* h);

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

heap_t* heap_create(size_t n) {
    heap_t* h = (heap_t*) malloc(sizeof(heap_t));
    assert(h);
    h->nb = 0;
    h->tab = (int*) malloc(sizeof(int)*n);

    return h;
}

void heap_free(heap_t* h) {
    free(h->tab);
    free(h);
}

void heap_insert(heap_t* h, int v) {
    assert(h);

    int pos = ++(h->nb);

    h->tab[pos] = v;
    while(pos != 1 && h->tab[pos/2] > h->tab[pos]) {
        swap(&h->tab[pos/2], &h->tab[pos]);
        pos/=2;
    }
}

int __min_child_pos(heap_t* h, int x) {
    if(x*2+1>h->nb || h->tab[x*2+1]>h->tab[x*2]) return x*2;
    return x*2+1;
}

int heap_getAndRemoveMin(heap_t* h) {
    assert(h);

    int ret = h->tab[1];
    h->tab[1] = h->tab[h->nb--];

    int pos=1,mcp;
    while(pos*2 <= h->nb && h->tab[(mcp=__min_child_pos(h, pos))] < h->tab[pos]) {
        swap(&h->tab[mcp], &h->tab[pos]);
        pos=mcp;
    }

    return ret;
}

int main(int argc, char const *argv[]) {
    heap_t* h = heap_create(300);

    srand(time(0));

    char done[200];
    int alea;
    memset(done, 0, 200);
    for(int i=0;i<200;i++) {
        alea = rand()%200;
        if(!done[alea]) {
            heap_insert(h, alea);
            printf("insert %d\n", alea);
            done[alea]=1;
        }
    }

    printf("NB : %d\n", )

    // for(int i=0; i<h->nb; i++) {
    //  printf("%d\n",heap_getAndRemoveMin(h));
    // }
    puts("");

    heap_free(h);

    return 0;
}