473,321 Members | 1,622 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,321 software developers and data experts.

Dynamic Priority Queue(heap) implementation

37
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:

Expand|Select|Wrap|Line Numbers
  1. int i= ++CurrentSize;
  2. while(i != 1 && X > heap[i/2])  {
  3. // cannot put x in heap [i]
  4. heap[i] = heap[i/2];  //move element down
  5. i /= 2;  /move to parent
  6. }
  7. heap[i] = x;
  8.  
So I created a .h file:

Expand|Select|Wrap|Line Numbers
  1. #ifndef queuedef
  2. #define queuedef
  3.  
  4. class Queue {
  5.        public:
  6.               int a;
  7.               int i;
  8.               class Queue *next;
  9.               Queue();
  10.               void insert(int a);
  11.               void deletetop();
  12.               int gettop();
  13.               void destroy();
  14.               void show();
  15. };
  16. #endif
  17.  
in which "i" is like the "i" of the static priority queue.

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

Expand|Select|Wrap|Line Numbers
  1. class Queue * gotofather(class Queue *temp1)
  2. {
  3.      class Queue *temp;
  4.      temp=top;
  5.      while((temp->i!=temp1->i/2)&&(temp->i!=1))
  6.               temp=temp->next;            
  7.      return temp;
  8. }
  9.  
  10. void Queue::insert(int data)
  11. {
  12.      class Queue *temp,*temp1;
  13.      int temp2;
  14.      temp=top;
  15.      top=(class Queue *) malloc(sizeof(class Queue));
  16.      top->a=data;
  17.      top->next=temp;
  18.      top->i=++CurrentSize;
  19.      temp=top;
  20.      temp1=gotofather(temp);
  21.      while((temp1->i!=1)&&(data>temp1->a))
  22.      {
  23.           temp->a=temp1->a;   //heap[i]=heap[i/2]
  24.           temp1=gotofather(temp1);   //i=i/2
  25.           temp=gotofather(temp);   //i=i/2
  26.      }
  27.      temp->a=data;//heap[i]=x
  28. }
  29.  
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
Jan 14 '09 #1
14 16893
Tassos Souris
152 100+
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
Jan 14 '09 #2
AlarV
37
@Tassos Souris
hahaha! ellhnas eisai? Well not actually 2 months but 1,5 so we'll see...
Jan 14 '09 #3
donbock
2,426 Expert 2GB
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.
Jan 14 '09 #4
AlarV
37
@donbock
Well I need it to be a max heap.

Like this:
Expand|Select|Wrap|Line Numbers
  1.  
  2.        36
  3.        /  \
  4.       4   5
  5.      / \ 
  6.     2  1
  7.  
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..
Jan 14 '09 #5
donbock
2,426 Expert 2GB
@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).
Jan 14 '09 #6
weaknessforcats
9,208 Expert Mod 8TB
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?
Jan 15 '09 #7
JosAH
11,448 Expert 8TB
@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
Jan 15 '09 #8
donbock
2,426 Expert 2GB
@weaknessforcats
One source of further information is Wikipedia: "binary heap" and "priority queue".
Jan 15 '09 #9
AlarV
37
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.
Jan 15 '09 #10
donbock
2,426 Expert 2GB
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.
Jan 15 '09 #11
AlarV
37
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:

Expand|Select|Wrap|Line Numbers
  1. class Queue * gotofather(class Queue *temp1)
  2. {
  3.      class Queue *temp;
  4.      temp=top;
  5.      while((temp->i!=temp1->i/2)&&(temp->i!=1))
  6.               temp=temp->next;            
  7.      return temp;
  8. }
  9.  
  10. void Queue::insert(int data)
  11. {
  12.      class Queue *temp,*temp1;
  13.      int temp2;
  14.      temp=top;
  15.      top=(class Queue *) malloc(sizeof(class Queue));
  16.      top->a=data;
  17.      top->next=temp;
  18.      top->i=++CurrentSize;
  19.      temp=top;
  20.      temp1=gotofather(temp);
  21.      while((temp1->i!=0)&&(data>temp1->a))
  22.      {
  23.           temp2=temp->a;
  24.           temp->a=temp1->a;
  25.           temp1->a=temp2;
  26.           temp1=gotofather(temp1);
  27.           temp=gotofather(temp);
  28.      }
  29. }
  30.  
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
Jan 15 '09 #12
AlarV
37
@donbock
What do u mean by the priority values being dynamic and not the whole queue? Could you explain it with an example?
Jan 15 '09 #13
JosAH
11,448 Expert 8TB
@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
Jan 16 '09 #14
donbock
2,426 Expert 2GB
@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".
Jan 16 '09 #15

Sign in to post your reply or Sign up for a free account.

Similar topics

0
by: aaronwmail-usenet | last post by:
I've been wondering about benchmarks recently. What is a fair benchmark? How should benchmarks be vetted or judged? I decided to see what you folks thought, so for discussion I compared two...
9
by: Tom | last post by:
What I mean is why can I only allocate const size stuff on the stack in C++? If I want to allocate a variable amount I need to use the OS API (Win32 in my case). Thanks, Tom.
4
by: Henk | last post by:
Hi, I am new to the c-programming language and at the moment I am struggling with the following: I want to read a file using fread() and then put it in to memory. I want to use a (singel)...
2
by: soniya_batra1982 | last post by:
I have a problem in imploementation of circular queue through array in C language. Please send me the code of functions for insertion, deletion and display the elements of array. Plz send me quick...
1
by: VanKha | last post by:
I write a queue program but it doesn't work properly:I enqueue an element and dequeue just after that, but the output is the first value and then many times of "Empty queue.."!Why ?Please help me. ...
3
by: shublakhan | last post by:
How to implement queue in C++ using pointers.
11
by: amolbehl | last post by:
Hi. Does anyone know how to implement queue in VB6.0 ? I just need the push function to push end of queue and pop to remove an item from top of the queue.
3
by: Stuart Golodetz | last post by:
Hi guys, Just wondering what you'd recommend in terms of a C++ priority queue implementation that supports bubble-up and bubble-down operations please? std::priority_queue doesn't seem to...
0
by: tabassumpatil | last post by:
Please send the c code for: 1.STACK OPERATIONS : Transfer the names stored in stack s1 to stack s2 and print the contents of stack s2. 2.QUEUE OPERATIONS : Write a program to implement...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.