Huffman implementation in C language

Huffman

#include <stdio.h>
#include <string.h>


struct CharAndFreq
{
    char ch;
    unsigned freq;
};


struct MinHeapNode
{
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};


struct MinHeap
{
    unsigned size;
    unsigned capacity;
    struct MinHeapNode **array;

};


void build_heap(struct MinHeap *minheap)
{
    int lenght = minheap->size - 1;
    for (int i = lenght / 2; i > -1; --i)
    {
        minheapify(minheap, i);
    }
}

struct MinHeap* createHeap(int capacity)
{
    struct MinHeap *minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode**) malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
    return minHeap;
} 


void minheapify(struct MinHeap *minheap, int i)
{
    int minimum, left, right;

    minimum = i;
    left = 2*i + 1;
    right = 2*i + 2;
    if (left < minheap->size && minheap->array[left]->freq < minheap->array[minimum]->freq)
    {
        minimum = left;
    }
    if (right < minheap->size && minheap->array[right]->freq < minheap->array[minimum]->freq)
    {
        minimum = right;
    }
    if (minimum != i)
    {
        swap(&minheap->array[minimum], &minheap->array[i]);
        minheapify(minheap, minimum);
    }
}

struct MinHeapNode* extract_min(struct MinHeap *minHeap)
{
    struct MinHeapMode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    minHeap->size--;
    minheapify(minHeap, 0);
    return temp;
}



void swap(struct MinHeapNode **one, struct MinHeapNode **two)
{
    struct MinHeapNode *temp = *one;
    *one = *two;
    *two = temp;
}


struct MinHeapNode* newNode(char data, int freq)
{
    struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL; // обнуляем указатели
    temp->data = data;
    temp->freq = freq;
    return temp;
}

void add(struct MinHeap *minHeap, struct MinHeapNode *minHeapNode)
{
    int i = minHeap->size;
    minHeap->size++;
    while(i > 0 && minHeapNode->freq < minHeap->array[(i - 1)/2]->freq) // непонятно
    {
        minHeap->array[i] = minHeap->array[(i - 1)/2];
        i = (i - 1)/2;
    }
    minHeap->array[i] = minHeapNode;
}


struct MinHeapNode* buildHuffmanTree(struct CharAndFreq *data, int size) // * добавил
{
    struct MinHeapNode *left, *right, *top;
    // создаем минимальную кучу
    struct MinHeap *minHeap = createHeap(size);

    for (int i = 0; i < size; ++i)
    {
        minHeap->array[i] = newNode(data[i].ch, data[i].freq);
    }
    minHeap->size = size;
    build_heap(minHeap);

    while(minHeap->size > 1)
    {
        left = extract_min(minHeap);
        right = extract_min(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        add(minHeap, top);
    }
    // последний элемент - корень
    return extract_min(minHeap);

}


void huffmanCodes(struct MinHeapNode* root, int *codes, int top)
{
    // Assign 0 to left edge and recur
    if (root->left)
    {
        codes[top] = 0;
        huffmanCodes(root->left, codes, top + 1);
    }
 
    // Assign 1 to right edge and recur
    if (root->right)
    {
        codes[top] = 1;
        huffmanCodes(root->right, codes, top + 1);
    }
 
    // If this is a leaf node, then it contains one of the input
    // characters, print the character and its code from codes[]
    if (root->left == NULL && root->right == NULL)
    {
        printf("%c: ", root->data);
        for (int i = 0; i < top; ++i)
            printf("%d", codes[i]);
        printf("\n");
    }
}

int main()
{
    char input[100];
    int j, lenght;  // частота вхождения символа
    struct CharAndFreq data[256];
    int k = 0;  // указатель на массив и кол-во массивов одновременно
    printf("Введите строку\n");
    gets(input);
    printf("---------------------\n");
    // printf("%s", input);
    lenght = strlen(input);
    for (int i = 32; i < 255; ++i)
    {
        j = 0;
        // printf("ASCII %d %c\n", i, i);
        data[k].freq = 0;
        while(input[j] != '\0')
        {
            if (input[j] == i)
            {
                data[k].freq++;
            }
            j++;
        }
        if (data[k].freq != 0) 
        {
            data[k].ch = i;
            k++;

        }
    }
    printf("Частота встречаемости символов:\n");
    for (int i = 0; i < k; ++i)
    {
        printf("%c %d\n", data[i].ch, data[i].freq);
    }

    struct MinHeapNode *root = buildHuffmanTree(data, k);
    int codes[256], top = 0;
    printf("---------------------\nHuffman codes:\n");
    huffmanCodes(root, codes, top);

    return 0;
}