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;
}
```