|
Thank you for this amazing piece of code. Saved me some precious time! 
|
|
|
|
|
thanks for sharing this project
|
|
|
|
|
becouse, for implementation the data structure need use templet in C#
|
|
|
|
|
was very usefull class for coding other algorithms like Hufman Code
|
|
|
|
|
|
First of all thanks to BenDi for your great PQ.
Only one feature that I want more is 'allow no duplicated value in list', so I decide to extend his code.
What I have done is just to perform the binary search before Push() any object in the list, just to check that it is already there or not. If it's there then we do nothing.
I choose binary search because this will limit the big-o to O(log N), so it will be like almost the same complexity with PQ.
(I'm not sure whether Contains() method in ArrayList() is perform in linear or binary so I do it for myself here.)
This is modified Push() method
public int Push(object O)
{
int p = InnerList.Count, p2;
if (CheckValueInList(O) == -1)
InnerList.Add(O);
else
return -99;
do
{
if (p == 0)
break;
p2 = (p - 1) / 2;
if (OnCompare(p, p2) < 0)
{
SwitchElements(p, p2);
p = p2;
}
else
break;
}while (true);
return p;
}
And the binary search method is here
int CheckValueInList(Object O)
{
if (InnerList.Count == 0)
return -1;
int low = 0;
int high = InnerList.Count - 1;
int mid;
while (low <= high)
{
mid = low + (high - low) / 2;
if (Comparer.Compare(InnerList[mid], O) < 0)
high = mid - 1;
else if (Comparer.Compare(InnerList[mid], O) > 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Any suggest is welcomed.
|
|
|
|
|
hi ! i am implemnting a program that first
* make Queue_Adt
* create a program structure
1. Create a program structure. It contains a float ProgramAge (or creationTime), and two imtegers programNumber and priority_level. ProgramNumber is a just like a counter. Program age can have values 0<ProgramAge<20
2. Create three queues of type program: QueueADT<program> low, high and mid.
3. Create a function program getNextProgram(), that creates a program, randomly assigns values to its programAge and priority_level (0,1 or 2) and returns the program. It also assigns value to programNumber. let programNumber = 0 for first program, programNumber=1 for second and so on.
4. Get a program from getNextProgram(). Based on the priority of the program, select the queue for the program.
5. Once the queue is decided, insert the program into the queue depending on its ProgramAge. The program with the highest ProgramAge should be in front of the queue.
6. Repeat 4-5, 20 times.
7. Write the configuration of each queue into file. For example file should look something like:
High:
ProgramNumber = 2, ProgramAge=3.5
ProgramNumber = 4, ProgramAge=2
…
Mid:
ProgramNumber = 0, ProgramAge=13.2
…
Low:
ProgramNumber = 3, ProgramAge=4.0
ProgramNumber = 1, ProgramAge=3.0
…
but stuck in step " 5 " also help me out how to put that data on text file :
sample code of main class is given
#include <iostream.h>
#include <conio.h>
#include "Queue.cpp"
#include <math.h>
class Programm{
private:
int prior_level,program_no;
float creation_time;
public:
Programm(){
program_no=0;
}
void set_id()
{
program_no++;
}
void set_time()
{
creation_time=(rand() % 20) + 1;
}
void set_prior()
{
prior_level=(rand() % 3) ;
}
int get_id()
{
return program_no;
}
float get_time()
{
return creation_time;
}
int get_prior()
{
return prior_level;
}
};
void main()
{
Queue<Programm> low,high,medium;
Programm p;
int pl,hl,ml=0;
for (int i=0;i<=20;i++)
{
p.set_prior();
if(p.get_prior()==0)
{
low.enQueue(p);
cout<<"the no of element in low ="<<low.Count()<<endl;
}
if(p.get_prior()==1)
{
medium.enQueue(p);
cout<<"the no of element in medium="<<medium.Count()<<endl;
}
if(p.get_prior()==2)
{
high.enQueue(p);
cout<<"the no of element in high="<<high.Count()<<endl;
}
}
getch();
}
mani
|
|
|
|
|
|
|
Ben Hi;
I am implementing this priority queue in a project but I am in need of the Remove method since I am new to programing wondering if you can help. 
|
|
|
|
|
I have a HashTable w/ integer values and would like to leave these sorted. When i try to put this into the PQ, it says that there is no IComparer. Is it possible to sort the values of the HashTable using this class?
|
|
|
|
|
Binary heaps are not necessarily the most efficient data structure for priority queues as you state in the introduction. It is normally a reasonably good and simple solution, though.
On the relative efficiency of priority queue algorithms (old article, but the algorithms haven't changed much):
http://doi.acm.org/10.1145/5684.5686
I would very much see a similar comparison on some contemporary processor architecture as the constant factors can be affected by cache hit behavior.
David K
|
|
|
|
|
|
Hi,
I have taken a look at it and I think that Synchronized wrapper is not correctly implemented. You just use the inner ArrayList synchronized wrapper, but it is not enough. In many methods you access that list more than once, so single accesses are thread-safe, but the whole method not.
Hence, while using this queue from multiple threads use
<br />
lock (priorityQueue.SyncRoot)<br />
{<br />
}<br />
Pavel
|
|
|
|
|
Hi,
In the beginning of the article, you mention Dijsktra's algorithm. Would you happen to know the means of implementing this algorithm with Priority Queue in C#? Or maybe someone else would. I would be really glad for any help in this.
ICQ: 99848968
email: v.ruzicka@gmail.com
|
|
|
|
|
i'm working on doing the same thing. I'm trying to replace my distance table w/ this PQ to improve the time it takes to get the minimum distance.
|
|
|
|
|
Hi,
Thank you for sharing this code. I am using it for some AI related implementations. I was wondering if this is the most up to date version? Because there is no remove functionality yet. I could try to implement it myself, but I thought it might be better to ask first .
|
|
|
|
|
Hi BenDi,
Under what license is priority queue distributed?
Thanks.
|
|
|
|
|
I don't understanbd what you're supposed to do if you want to change an object's key while it's in the priority queue and then re-enforce the queue. Can you post a small example of what you mean in the instructions for Update()?
|
|
|
|
|
A PQ does not hold key-value-pairs. Rather, it uses the IComparable interface of the objects. So if you in any way change some member of an object already in the PQ, it might change the relation to other object, meaning that the queue is inconsistent. Only in that case should you call Update to force the queue to relocate that specific object to make the queue consistent. I coudnt think of a small example (stuff like that does not happen in small examples), I hope you understand it anyway 
|
|
|
|
|
I also had a need to do this, so I derived a class which handles it.
It does this by using a key-value lookup (in mObjectIndex) and updating this after any operation on the queue. Note: this means changing the base class by 1) making sure all the methods this overriding are virtual and 2) renaming Update to UpdateIndex. Also, one of the constructors from the original is missing.
It definitely will take a performance hit to do these operations, but if you need it, here it is.
Kudos to BenDi for posting the base class.
///
/// Adds update functionality to objects in the priority queue
///
public class BinaryPriorityQueueWithUpdate : BinaryPriorityQueue
{
private Hashtable mObjectIndex;
///
/// Determines whether the specified BinaryPriorityQueue contains object.
///
/// <param name="obj" />The obj.
public bool ContainsObject(object obj)
{
return mObjectIndex.Contains(obj);
}
#region contructors
///
/// Initializes a new instance of the <see cref="BinaryPriorityQueueWithUpdate"> class.
///
public BinaryPriorityQueueWithUpdate() : base()
{
mObjectIndex = new Hashtable();
}
///
/// Initializes a new instance of the <see cref="BinaryPriorityQueueWithUpdate"> class.
///
/// <param name="comparer" />The comparer.
public BinaryPriorityQueueWithUpdate(IComparer comparer) : base(comparer)
{
mObjectIndex = new Hashtable();
}
///
/// Initializes a new instance of the <see cref="BinaryPriorityQueueWithUpdate"> class.
///
/// <param name="capacity" />The capacity.
public BinaryPriorityQueueWithUpdate(int capacity) : base(capacity)
{
mObjectIndex = new Hashtable(capacity);
}
///
/// Initializes a new instance of the <see cref="BinaryPriorityQueueWithUpdate"> class.
///
/// <param name="comparer" />The comparer.
/// <param name="capacity" />The capacity.
public BinaryPriorityQueueWithUpdate(IComparer comparer, int capacity) : base(comparer, capacity)
{
mObjectIndex = new Hashtable(capacity);
}
#endregion
///
/// Get the smallest object and remove it.
///
/// <returns>The smallest object
public override object Pop()
{
mObjectIndex.Remove(InnerList[0]);
if (InnerList.Count > 0)
{
mObjectIndex.Remove(InnerList[InnerList.Count-1]);
mObjectIndex.Add(InnerList[InnerList.Count-1], 0);
}
return base.Pop();
}
///
/// Push an object onto the PQ
///
/// <param name="obj" />The new object
/// <returns>
/// The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.
///
public override int Push(object obj)
{
mObjectIndex.Add(obj, InnerList.Count);
return base.Push(obj);
}
///
/// Switches the elements.
///
/// <param name="i" />The i.
/// <param name="j" />The j.
protected override void SwitchElements(int i, int j)
{
object iObj = this.InnerList[i];
object jObj = this.InnerList[j];
mObjectIndex.Remove(iObj);
mObjectIndex.Remove(jObj);
mObjectIndex.Add(iObj, j);
mObjectIndex.Add(jObj, i);
base.SwitchElements (i, j);
}
///
/// Updates the specified obj.
///
/// <param name="obj" />The obj.
/// <param name="newObj" />The new obj.
public void Update(object obj, object newObj)
{
int index = (int) mObjectIndex[obj];
mObjectIndex.Remove(obj);
mObjectIndex.Add(newObj, index);
InnerList[index] = newObj;
base.UpdateIndex(index);
}
///
/// Updates the specified obj.
///
/// <param name="obj" />The obj.
public void Update(object obj)
{
int index = (int) mObjectIndex[obj];
base.UpdateIndex(index);
}
}
|
|
|
|
|
wow!! u posted it on very rite time.. i had been looking for heap implementation for last 5-10 days.. Thanks
Muhammad Shoaib Khan
http://geocities.com/lansolution
|
|
|
|
|
Why did you need this class as oposed to the Queue collection class that comes with the Framework?
|
|
|
|
|
There are several reasons:
First of all, Queue is less flexible: you can only enqueue/dequeue at the tail, there is no indexed access. Dequeue adds that flexibility with no loss of performance (enqueuing to the head is as fast as enqueuing to the tail).
Second, I think that all those System.Collection classes are a bit unfriendly. They have all their data members as 'protected internal', so you dont have a chance of really extending any of them - you just dont have access to the data core or other important members.
So from time to time its quite useful to write a new implementation of a collection, even if it adds not that much to the present functionality.
Take care,
Ben
|
|
|
|
|
Sorry, its even worse: ArrayList has its data core 'private' - just had a look at the IL.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
