Dynamic Priority Queue(heap) implementation

[AlarV]

Hello everyone, here is my problem. I have to make a dynamic priority queue,which is a heap, and my book isn't helpful at all, so I have no clues on how to create it.. I read something like a static priority queue, which is an array heap[i], and for example i/2 is the father of i and so on..
the code of the static priority queue is this:

int i= ++CurrentSize;
while(i != 1 && X > heap[i/2])  {
// cannot put x in heap [i]
heap[i] = heap[i/2];  //move element down
i /= 2;  /move to parent
}
heap[i] = x;
 

So I created a .h file:

#ifndef queuedef
#define queuedef
 
class Queue {
       public:
              int a;
              int i;
              class Queue *next;
              Queue();
              void insert(int a);
              void deletetop();
              int gettop();
              void destroy();
              void show();
};
#endif
 

in which "i" is like the "i" of the static priority queue.

Here is the code of the main file(only insert):

class Queue * gotofather(class Queue *temp1)
{
     class Queue *temp;
     temp=top;
     while((temp->i!=temp1->i/2)&&(temp->i!=1))
              temp=temp->next;            
     return temp;
}
 
void Queue::insert(int data)
{
     class Queue *temp,*temp1;
     int temp2;
     temp=top;
     top=(class Queue *) malloc(sizeof(class Queue));
     top->a=data;
     top->next=temp;
     top->i=++CurrentSize;
     temp=top;
     temp1=gotofather(temp);
     while((temp1->i!=1)&&(data>temp1->a))
     {
          temp->a=temp1->a;   //heap[i]=heap[i/2]
          temp1=gotofather(temp1);   //i=i/2
          temp=gotofather(temp);   //i=i/2
     }
     temp->a=data;//heap[i]=x
}
 

I know it's kind of hard to read the whole code, but please I would appreciate it if you did. My university is closed (due to strike) and we didn't have any lessons for the past 2 months. I thank anyone who will reply and give me at least some clues, if what I'm doing is right or totally wrong. Thanks in advance!

Kind regards, AlarV

[donbock]

Do you maybe mean to create the priority queue on the heap? That is, create it dynamically?

Well it's not really clear to me, but what I got from the lesson is that a priority queue could be a heap. That's why I wrote it like that. And yes I have to make it dynamic too.

I'm pretty sure that the word "dynamic" in "dynamic priority queue" refers to the priority values being dynamic not that the queue be kept in dynamic [heap] memory ... although it may well be malloc'ed.

The trick is that the heap is ordered by priority, so you have to rearrange it when a task priority value changes.

[AlarV]

Well due to what you said and the article from Wikipedia,that donbock suggested, I re-changed the "insert" and now it seems to work properly, here is the code:

class Queue * gotofather(class Queue *temp1)
{
     class Queue *temp;
     temp=top;
     while((temp->i!=temp1->i/2)&&(temp->i!=1))
              temp=temp->next;            
     return temp;
}
 
void Queue::insert(int data)
{
     class Queue *temp,*temp1;
     int temp2;
     temp=top;
     top=(class Queue *) malloc(sizeof(class Queue));
     top->a=data;
     top->next=temp;
     top->i=++CurrentSize;
     temp=top;
     temp1=gotofather(temp);
     while((temp1->i!=0)&&(data>temp1->a))
     {
          temp2=temp->a;
          temp->a=temp1->a;
          temp1->a=temp2;
          temp1=gotofather(temp1);
          temp=gotofather(temp);
     }
}
 

It seems that it was easier than I thought. However I still have my doubts, as I created it all by myself, and the project might need some kinds of templates.

Should I have all the code in the main file or it could be somewhere else? For example could i have this code at an .h file?

Thanks everyone again, u've been very helpful!

Kind regards,
AlarV

[AlarV]

@donbock
What do u mean by the priority values being dynamic and not the whole queue? Could you explain it with an example?

[JosAH]

@AlarV
Maybe you should read that article in the Java Howtos section. I wrote it and of course I didn't invent it. Basically you need one method/function: one that bubbles a number up in the heap in order to put it in place. That algorithm is described in detail in that article.

The check whether or not both children exist for a node is just a small coding burden,

kind regards,

Jos

[donbock]

@AlarV
When you add a node to the heap, you determine its position based on the priority value stored within it. There are a number of ways in which a task's priority can be altered. If the priority value of a node changes then the heap is no longer order properly -- you must rearrange it. I believe that this dynamicism is what is commonly meant by a "_dynamic_ priority queue".