why are the nodes of my huffman code not sorted properly? C

Question

I am trying to debug my Huffman Code and found out the when I am calling my buildHuffmanTree and printing the nodes of my minHeap using the print function that I commented out below, I get a Segmentation Fault: 11 because I only have 5 nodes in my Huffman tree when I'm expecting there to be 11 made of the original 6 letters, plus the 5 internal nodes that are the sum of their frequencies. Could someone please help me figure out how to fix this?

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

    #define SIZE 100000

    char arr[SIZE];
    int  freq[SIZE]; 
    int  arr2[SIZE]; 

    int qTop = 0;
    int size=0;

    struct node{

        char data;
        int frequency;
        struct node* left;
        struct node* right;
    };

    struct node* PQ[SIZE];

    struct node* newNode(char data, int frequency){

        struct node* t = (struct node*)malloc(sizeof(struct node)); 
        t->data = data;
        t->frequency= frequency; 
        t->left = NULL; 
        t->right = NULL; 
        return (t); 
    }



void minHeapify(struct node* PQ[], int x){

    int frequency = PQ[x]->frequency;
    char data = PQ[x]->data;
    int i=x;  //the current node
    int j= 2*i; //the left node
    while(j<=qTop){
        if (j<qTop && (PQ[j+1]->frequency < PQ[j]->frequency)){
            j=j+1; //the right node
        }
        if (PQ[j]->frequency < frequency){
            PQ[i]->frequency = PQ[j]->frequency;
            PQ[i]->data = PQ[j]->data;
            i=j;
            j=2*i;
        } else{
            break;
        }
    }

}

void push(struct node* PQ[], struct node* node){

    if (qTop==SIZE){
        printf("PQ OVERFLOW \n");
    } else{
        qTop=qTop+1;
        int i = qTop;
        int j = (int)(i/2);
        while (i > 1 && PQ[j]->frequency > node->frequency){
            PQ[i] = PQ[j];
            i = j;
            j = (int)(i/2);
        }
        PQ[i] = node;
    }
}

struct node* pop(struct node* PQ[]){

    if (qTop==0){
        printf("PQ UNDERFLOW \n");
        return NULL;
    } else{
        struct node* node = PQ[1];
        PQ[1] = PQ[qTop];
        qTop = qTop - 1;
        minHeapify(PQ,1);
        return node;
    }

}

void printCodes(struct node* root, int arr2[], int top) {  

    if (root->left) { 
        arr2[top] = 0; 
        printCodes(root->left, arr2, top + 1); 
    } 

    if (root->right) { 
        arr2[top] = 1; 
        printCodes(root->right, arr2, top + 1); 
    } 

    if (root->left == NULL && root->right == NULL) { 
        printf("%c: ", root->data); 
        for (int i = 0; i < top; i++){
            printf("%d", arr2[i]); 
        } 
        printf("\n"); 

    } 
}

void buildHuffmanTree(char arr[], int freq[]){

    for (int i=0;i<strlen(arr);i++){
        struct node* node = newNode(arr[i],freq[i]);
        push(PQ,node);
        size++;
    }
    int PQsize=0;
    for (int i=1; i<size;i++){
        PQsize++;
        struct node* node2 = newNode('!',0);
        node2->left = pop(PQ);
        node2->right = pop(PQ);
        struct node* nodeL=node2->left;
        struct node* nodeR=node2->right;
        node2->frequency = nodeL->frequency + nodeR->frequency;
        push(PQ,node2);
    }

    /*
    for (int i=1;i<PQsize,i++){
        printf("%c:%d \n",PQ[i]->data,PQ[i]->frequency);
    }
    */
    struct node* root= pop(PQ);
    int top=0;
    printCodes(root,arr2,top);
}

int main(){

    char arr[] = "abcdef"; 
    int freq[] = { 5, 9, 12, 13, 16, 45 }; 

    buildHuffmanTree(arr,freq);

    return 0;
}

When I run the print that is commented out function, I get:

!:100 
!:55 
!:30 
e:16 
d:13 
b:9 
Segmentation fault: 11

and as a result, my encoding is wrong and my program outputs:

c: 00
a: 010
b: 011
!: 10
!: 110
e: 111

instead of:

a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

Please help me understand why all my node getting jumbled once I insert them into my minHeap. Thank you.

Answer 1

PQ is an array of pointers. When push is called for the first time, nothing has been assigned to any of these pointers. push executes:

    qTop=qTop+1;
    int i = qTop;
    int j = (int)(i/2);
    while (i > 0 && PQ[j]->frequency > node->frequency){

At this point, i is greater than zero, but PQ[j] has not been assigned a value. The behavior of the program is undefined from this point on.