Min-Priority Queue using a binary heap

filapri.c

#include <malloc.h>
#include "filapri.h"

static inline int pri_menor(filapri f, size_t ind_a, size_t ind_b);
static inline void troca_nodo(filapri f, size_t ind_a, size_t ind_b);
static void arruma_heap_up(filapri f);
static void arruma_heap_down(filapri f, size_t k);

int pri_menor(filapri f, size_t ind_a, size_t ind_b)
{
    return f->pri[ind_a] < f->pri[ind_b];
}

void troca_nodo(filapri f, size_t ind_a, size_t ind_b)
{
    // troca prioridades de a e b
    long int pri_t = f->pri[ind_a];
    f->pri[ind_a] = f->pri[ind_b];
    f->pri[ind_b] = pri_t;
    // troca conteudo de a e b
    void * t = f->conteudo[ind_a];
    f->conteudo[ind_a] = f->conteudo[ind_b];
    f->conteudo[ind_b] = t;
}

filapri constroi_filapri(size_t capacidade)
{
    filapri nova_fila = malloc(sizeof(struct filapri_t));
    if (nova_fila == NULL) return NULL;
    nova_fila->tamanho = 0;
    nova_fila->capacidade = capacidade;
    nova_fila->pri = (long int *) malloc(sizeof(long int) * (capacidade+1));
    nova_fila->conteudo = (void **) malloc(sizeof(void *) * (capacidade+1));
    if (nova_fila->conteudo == NULL) {
        free(nova_fila);
        return NULL;
    }
    return nova_fila;
}

int destroi_filapri(filapri f, int (*destroi_conteudo)(void *))
{
    if (f == NULL) return 0;
    else if (f->conteudo != NULL) {
        if (destroi_conteudo != NULL) {
            for(size_t i = 0; i < f->capacidade; ++i) {
                if (i < f->tamanho) {
                    destroi_conteudo(f->conteudo[i]);
                }
            }
        }
        free(f->conteudo);
        free(f->pri);
    }
    free(f);
    return 1;
}

size_t tamanho_filapri(filapri f)
{
    if (f == NULL) return 0;
    return f->tamanho;
}

int vazia_filapri(filapri f)
{
    return tamanho_filapri(f) == 0;
}

void arruma_heap_up(filapri f)
{
    size_t k = f->tamanho;
    size_t pai = f->tamanho / 2;
    while(k > 1 && pri_menor(f, k, pai)) {
        // chave do pai menor que a do filho, troca
        troca_nodo(f, pai, k);
        // sobe um nivel em direcao a raiz na heap
        k = pai;
        pai = k / 2;
    }
}

void arruma_heap_down(filapri f, size_t k)
{
    const size_t n = f->tamanho - 1;
    size_t j;
    while(2*k <= n) {
        // j recebe o filho a esquerda do nodo k
        j = 2*k;
        if (j < n && pri_menor(f, j+1, j)) {
            // nodo da direita tem prioridade menor que o da esquerda,
            // escolhe o nodo da direita para verificar
            j++;
        }
        if (!pri_menor(f, j, k)) {
            // prioridade do filho nao eh menor que do pai, propriedade do
            // min-heap mantida
            break;
        }
        // troca pai com filho
        troca_nodo(f, k, j);
        // k recebe o indice de seu filho
        k = j;
    }
}

int insere_filapri(filapri f, long int pri, void * conteudo)
{
    if (f->tamanho == f->capacidade) {
        // fila cheia, tenta dobrar a capacidade da fila
        f->capacidade = 2 * f->capacidade;
        f->pri = realloc(f->pri, sizeof(long int) * (f->capacidade+1));
        if (f->pri == NULL) return 0;
        f->conteudo = realloc(f->conteudo, sizeof(void *) * (f->capacidade+1));
        // falhou em realocar memoria para os nodos do heap, devolve 0
        if (f->conteudo == NULL) return 0;
    }
    f->tamanho++;
    f->pri[f->tamanho] = pri;
    f->conteudo[f->tamanho] = conteudo;
    arruma_heap_up(f);
    return 1;
}


void * remove_min_filapri(filapri f)
{
    if (f == NULL) return NULL;
    else if (vazia_filapri(f)) return NULL;
    troca_nodo(f, 1, f->tamanho);
    arruma_heap_down(f, 1);
    return f->conteudo[f->tamanho--];
}

filapri.h

#ifndef __FILAPRI_H_
#define __FILAPRI_H_

struct filapri_t {
    size_t tamanho;
    size_t capacidade;
    long int * pri;
    void ** conteudo;
};

typedef struct filapri_t* filapri;

/*! Cria uma fila de prioridade
 * \param capacidade Capacidade inicial da fila
 * \return Caso a fila seja alocada com sucesso, devolve ponteiro para estrutura
 * da fila. Devolve NULL caso contrário.
 */
filapri constroi_filapri(size_t capacidade);

int destroi_filapri(filapri f, int (*destroi_conteudo)(void *));

size_t tamanho_filapri(filapri f);

int vazia_filapri(filapri f);

int insere_filapri(filapri f, long int pri, void * conteudo);

void * remove_min_filapri(filapri f);

#endif