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_q ueue 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.