Priority queue implementation on C. (For Huffman Coding)

Question

I trying to implement Huffman Codes on C. And, since my previous attempt failed, I decided to approach the issue more responsibly. So I'm asking for feedback on my implementation of the priority queue on C. First of all, the design of structures and interfaces is important to me! Also, how easy would it be to implement a Huffman tree using this structure? And of course, what about decomposition?

priority_queue.h

#ifndef PRIORITY_QUEUE
#define PRIORITY_QUEUE
#include <stdlib.h>
struct pq_node {
    unsigned long frequency;
    struct pq_node *parent;  //Pointers for Huffman tree
    struct pq_node *left;
    struct pq_node *right;
    char symbol;
};

struct priority_queue {
    struct pq_node *heap_on_array;
    size_t size;
    size_t capacity;
};

void init_queue(struct priority_queue **pq, size_t capacity);

void shift_up(struct priority_queue **pq, int i);  // i - index

void shift_down(struct priority_queue **pq, size_t i);  // i - index

struct pq_node extract_min(struct priority_queue **pq);

void insert(struct priority_queue **pq, char symbol);

void insert_element(struct priority_queue **pq, char symbol, unsigned long frequency);

void node_swap(struct pq_node *first, struct pq_node *second);

priority_queue.c

#include "priority_queue.h"
void init_queue(struct priority_queue **pq, size_t capacity)
{
    (*pq) = malloc(sizeof(struct priority_queue));
    (*pq)->heap_on_array = malloc(sizeof(struct pq_node) * capacity);
    (*pq)->capacity = capacity;
    (*pq)->size = 0;
};

void shift_up(struct priority_queue **pq, int i)
{
    while ((*pq)->heap_on_array[i].frequency < (*pq)->heap_on_array[(i-1)/2].frequency)
    {
        node_swap(&((*pq)->heap_on_array[i]), &((*pq)->heap_on_array[(i-1)/2]));
        i = (i - 1) / 2;
    }
}

void shift_down(struct priority_queue **pq, size_t i)
{
    while ((2 * i + 1) < (*pq)->size)
    {
        size_t left = 2 * i + 1;
        size_t right = 2 * i + 2;
        size_t j = left;
        if((right < (*pq)->size) && ((*pq)->heap_on_array[right].frequency < (*pq)->heap_on_array[left].frequency))
        {
            j = right;
        }
        if((*pq)->heap_on_array[i].frequency <= (*pq)->heap_on_array[j].frequency)
        {
            break;
        }
        node_swap(&((*pq)->heap_on_array[i]), &((*pq)->heap_on_array[j]));
        i = j;
    }
}

struct pq_node extract_min(struct priority_queue **pq)
{
    struct pq_node tmp = (*pq)->heap_on_array[0];
    (*pq)->heap_on_array[0] = (*pq)->heap_on_array[(*pq)->size - 1];
    (*pq)->size--;
    shift_down(pq, 0);
    return tmp;
}

void insert(struct priority_queue **pq, char symbol)
{
    for(size_t i = 0; i < (*pq)->size; ++i)
    {
        if((*pq)->heap_on_array[i].symbol == symbol)
        {
            (*pq)->heap_on_array[i].frequency++;
            shift_down(pq, i);
            return;
        }
    }
    
    if((*pq)->size == (*pq)->capacity)
    {
        (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
        (*pq)->capacity = (*pq)->capacity * 2;
    }
    (*pq)->size++;
    (*pq)->heap_on_array[(*pq)->size - 1].symbol = symbol;
    (*pq)->heap_on_array[(*pq)->size - 1].frequency = 1;
    shift_up(pq, (*pq)->size - 1);
}

void insert_element(struct priority_queue **pq, char symbol, unsigned long frequency)
{
    for(size_t i = 0; i < (*pq)->size; ++i)
    {
        if((*pq)->heap_on_array[i].symbol == symbol)
        {
            (*pq)->heap_on_array[i].frequency = frequency;
            shift_down(pq, i);
            return;
        }
    }

    if((*pq)->size == (*pq)->capacity)
    {
        (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
        (*pq)->capacity = (*pq)->capacity * 2;
    }
    (*pq)->size++;
    (*pq)->heap_on_array[(*pq)->size - 1].symbol = symbol;
    (*pq)->heap_on_array[(*pq)->size - 1].frequency = frequency;
    shift_up(pq, (*pq)->size - 1);
}

void node_swap(struct pq_node *first, struct pq_node *second)
{
    struct pq_node tmp = *first;
    *first = *second;
    *second = tmp;
}
```

Answer 1

• Avoid double pointers. They are absolutely unwarranted in all the functions (except init, but see below).

• Prefer returning a value to a side effect. In the client code, which I presume is along the lines of

    struct priority_queue * pq;
    init_queue(&pq, capacity);
  

  I have to read the source of init_queue to see that there is a side effect of modifying the parameter I passed. Compare it to a clear assignment:

    struct priority_queue * pq;
    pq = init_queue(capacity);
  

• Always test what malloc returns, and return NULL immediately if it fails. Ditto for reallocarray.

  Also, the blind

    (*pq)->heap_on_array = reallocarray((*pq)->heap_on_array, (*pq)->size * 2, sizeof(struct pq_node));
  

  leads to a memory leak in case of failure: the pointer to the original block is lost, and it cannot be freed. Typically one would

    temp = reallocarray(...);
    if (temp == NULL) {
        // handle_error, e.g. free(pq->heap_on_array);
        return;
    }
    pq->heap_on_array = temp;
  

• No naked loops. Every loop implements an important algorithm, and deserves a name. In your case, the initial loop of insert_* is surely

    pq_node * find(priority_queue * pq, char symbol);
  

• DRY. insert and insert_element are suspiciously similar. The only difference is in treating frequency. The common functionality shall be factored out into a function.

Answer 2

in function:

void init_queue(struct priority_queue **pq, size_t capacity)

after the final closing brace '}' there is a semicolon ';'. This results in the compiler outputting:

untitled1.c:41:2: warning: ISO C does not allow extra ‘;’ outside of a function [-Wpedantic]

There are also some warnings about implicit conversions.

When compiling, always enable the warnings, then fix those warnings.

for gcc, at a minimum use:

-Wall -Wextra -Wconversion -pedantic -std=gnu11 

Note: other compilers use different options to produce the same results.

the file: priority_queue.h is missing the statement:

#endif

at the end of the file. So it does not compile!