priority queue, where to insert?

Question

so I am having trouble implementing priority queue. For a priority queue, I need to find the first place where it is empty...that's where the element go, we will swap later..but I am having trouble figuring out the algorithm to find it.

Here's what I have so far:

void pq_insert(struct tnode* p)
{
    struct tnode* curr=NULL;
    struct tnode* prev=NULL;
   printf("inserting:%c,%f\n",p->symbol,p->freq);
   if(qhead==NULL) /*qhead is null*/
   {
    qhead = p;
        /*TODO: write code to insert when queue is empty*/
   }
   /*TODO: write code to find correct position to insert*/
    curr = qhead;
    while (curr != NULL){//I think this is wrong
        if ((curr -> left) == NULL){
            curr = curr -> right;
        }
        else{
            curr = curr -> left;
        }   
    }

   if(curr==qhead)
   {
        /*TODO: write code to insert before the current start*/

   }
   else /*insert between prev and next*/
   {
        /*TODO: write code to insert in between*/
   }
}

Answer 1

Yes, the code you think is wrong:

while (curr != NULL){//I think this is wrong
    if ((curr -> left) == NULL){
        curr = curr -> right;
    }
    else{
        curr = curr -> left;
    }   
}

is wrong. You are navigating curr to some part of your tree regardless of your current node.

You probably want to change your inner if to something like:

if (p->freq < curr->freq)

Answer 2

I don't know exactly what you are doing with this while-loop.

while (curr != NULL){//I think this is wrong
    if ((curr -> left) == NULL){
        curr = curr -> right; // Why to go right here?!, isn't this an empty node?
    }
    else{
        curr = curr -> left;
    }   
}

If I am looking for the nearest empty (NULL) left node, I will do this

while (curr != NULL){
    if ((curr -> left) == NULL){//The left node is NULL. Great, I found empty node.
        curr = NULL;
    }
    else{ //hmmm, left node is not empty. Lets go left for more nodes. 
        curr = curr -> left;
    }   
}

But like this, searching will be going left-only. after some inserts the tree will not be balanced.

If you give more details, it will be more clear.