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

[Tassos Souris]

If you had a strike for 2 months then you are probably loosing the semester so do not bother making the project :P:P:P

[AlarV]

@Tassos Souris
hahaha! ellhnas eisai? Well not actually 2 months but 1,5 so we'll see...

[donbock]

Please explain what a dynamic priority queue(heap) is. If priority is dynamic, then what events can cause it to change?

I believe the meaning of this term is open to interpretation, so I would like to hear what you need it to be.

[AlarV]

@donbock
Well I need it to be a max heap.

Like this:

 
       36
       /  \
      4   5
     / \ 
    2  1
 

here for example 4 is the father of 2,1. and 36 is the father of 4,5

It's not really clear to me too, on how a heap's priority is assigned. In my book it says that you check (each time when you insert one number) the father, and then the father of the father and so on..

[donbock]

@AlarV
This looks like a "binary heap" sorted by priority. A binary heap has two basic explicit operations and several implicit operations:
> explicit: add a node to the heap;
> explicit: remove the root node from the heap;
> implicit: create the heap;
> implicit: destroy the heap;
> implicit: create a heap node;
> implicit: destroy a heap node.

To make this a _dynamic_ priority heap you need to add one more explicit operation:
> explicit: change the priority of a node in the heap (and rearrange the heap accordingly).

[weaknessforcats]

If memory serves, a priority queue is a data structure where values are inserted randomly but when extracted reppear in descending sequence. That is, a fetch from the priority queue always returns the element with the highest value.

Determination of the highest value is usually left to a callback function so the values can be returned in the order specified in the callback function.

Usual implementations accomplish this by keeping the containter sorted at all times so the highest value is always at the beginning of the queue.

Now a Heap is a data structure constructed such that the number of levels between the root and the farthest leaves is constant.

So I am having trouble digesting the phrase "priority queue that is a heap".

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

But the thing that really bugs me is that you are using C++ but are not using the already written priority_queue template in the C++ Standard Library. Why is that? Are you taking a class in archaeological computer science?

[JosAH]

@weaknessforcats
That is not true; usual implementations keep the heap a heap, i.e. for a parent P and two childs L and R, the relation P >= L && P >= R is true. (both L and R may not exist of course).

In the 'Generic Heap Sort' article in the Java Howtos that algorithm is described in detail. Keeping the entire thing sorted at all times is overkill.

kind regards,

Jos

[donbock]

@weaknessforcats
One source of further information is Wikipedia: "binary heap" and "priority queue".

[AlarV]

First of all I'd like to thank anyone, who tried to solve my problem, I appreciate it!
To answer to some of you
@weaknessforcats
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.

Well the "priority_queue template" is something that I don't know, (or I could say not have been taught yet, due to the strikes of the past 2 months).

Generally what I have to do is a project that contains some kinds of data structures,that we create by ourselves.

@JosAH: So what you are saying is that I should have 2 variables for each clue of the heap, which are the children of it(even if they don't exist), and check the max each time. This sounds right but the implementation might
not be as easy as it seems... I agree that "Keeping the entire thing sorted at all times is overkill." and that's why I came here :D. I already did that(having the whole heap sorted) and I could say that it is easy.

[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".