|
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.
|
|
|
|
|
Perhaps I miss your point. You did mention the abiblity to quickly locate items located in a Priority Queue Heap. This is not so much a Cicular Array or Array List object (like Queue) as it is a Clustered Index or Heap with feild identity.
I just spent to many hours writing C and C++ Circular arrays by hand to not enjoy being able to place a custom collection into a queue with a few line of code.
Queue was written to create a FIFO arraylist that can be pupolated by any collection of objects. enqueue/dequeue has been the sytax for working with a FIFO buffer since they were created. Push/Pop is syntax that is used for putting items a Stack or FILO(First In Last Out) using it to poplate items in a queue is confusing.
One thing that I find is a must when using this class (or any object that consumes or inherits array list) is to create an indexed custom collection class of the items that I am placing into the Queue. Then I sort or order the collection according to order I want them to run and copy to my Queue. This gives me an Indexed, Enumerable, serializable Array List object that follows FIFO logic and is thread safe.
|
|
|
|
|
uh, sh*t, my mistake... best you forget all about my answer, because I thought I was in a different project.
First of all: the reason I mixed this up is because I posted a Dequeue to codeproject. This one does what I described: a Queue where you can enqueue/dequeue from head and tail, both in O(1).
Now to the priority queue:
It has nothing to do with System.Collections.Queue. The purpose of a PQ is to have a structure that always has its smallest element at the top. You can push an item and the PQ will reorganize (in O(ld n), not O(n*log n) what would be nesseccary for sorting). And you can normally only pop the smallest item. Then the PQ will reorganize so the next smallest item is on top and so on. Its quite useful for many algorithms (shortest path for instance).
Well, in fact I dont quite understand the question 'what is wrong with queue?' because the PQ here has not that many similiarities to Queue...
And could you please explain what you meant in the last paragraph? Isnt that not what ICollection.CopyTo is designed for? But maybe I missed you point...;)
Take care,
Ben
|
|
|
|
|
Hey, I hope you don't mind, but I converted your code to Visual Basic. I wanted to make sure I understood it properly. I'm still trying to learn C#.
I've blogged about it.
http://www.enigmativity.com/blog/PermaLink.aspx?guid=3abe5bc8-d9bc-4cd3-a58a-3c1bf9b2d3ee
James R-S.
http://www.enigmativity.com/blog
|
|
|
|
|
Cool! Didnt exactly expect anyone to actually use it that fast . I see you made some changes to the code (extract ascend, descend). Check out the new version as well, i put up an interface for other PQ implementations - im working on a FibonacciPQ which is (supposed to be) faster.
Take care,
Ben
|
|
|
|
|