 |
AppletTalk.com
Java discussions newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Michael
Guest
|
 Posted: Tue Nov 14, 2006 1:35 am Post subject: Priority Queue implemented as LinkedList api class java |
 |
|
Hello all, its been a while. cheers to all. Anyways, I have been struggling
with what is suppose to be an "Easy" problem. Someone once told me that
things are easy only when obvious. I guess my problem then is this isn't
obvious to me. I have to implement a priority queue by means of the
LinkedList class found in the api.
I know the following:
I will have to use generics(which i will use after I get this working first
with integer data types)
When generics is in play I will have to implement the Comparable interface
with the compareTo method to compare keys.(which should be fun)
next,
I will have an Entry class as an innerclass within my Priority queue class.
I will have to print out both the key and value pairs based on minimum
key(highest priority).
However, by using the LinkedList class, I am almost certain I have to use an
iterator to step through all entries in the PQ and return the one with the
minimum key.
I guess I don't really understand how I am going to do this.
I am thinking store the first entry in a temp variable and compare the rest
of the entries with this one in regards to the key? When the minimum key is
found return the entry corresponding to it
I also tried to insert entries based on their keys into the list, however,
when I did this I got size 0 index 1000 error. Furthermore, if someone could
please lead a helping hand it would be much appreciated. I know this must
seem very trivial, but it isn't for me. At the moment I think implementing
this from scratch or with an array would have been much easier.
Thanks Mike |
|
| Back to top |
|
 |
Patricia Shanahan
Guest
|
| Posted: Tue Nov 14, 2006 8:11 am Post subject: Re: Priority Queue implemented as LinkedList api class java |
|
|
Michael wrote:
| Quote: | Hello all, its been a while. cheers to all. Anyways, I have been struggling
with what is suppose to be an "Easy" problem. Someone once told me that
things are easy only when obvious. I guess my problem then is this isn't
obvious to me. I have to implement a priority queue by means of the
LinkedList class found in the api.
I know the following:
I will have to use generics(which i will use after I get this working first
with integer data types)
When generics is in play I will have to implement the Comparable interface
with the compareTo method to compare keys.(which should be fun)
next,
I will have an Entry class as an innerclass within my Priority queue class.
I will have to print out both the key and value pairs based on minimum
key(highest priority).
However, by using the LinkedList class, I am almost certain I have to use an
iterator to step through all entries in the PQ and return the one with the
minimum key.
I guess I don't really understand how I am going to do this.
I am thinking store the first entry in a temp variable and compare the rest
of the entries with this one in regards to the key? When the minimum key is
found return the entry corresponding to it
I also tried to insert entries based on their keys into the list, however,
when I did this I got size 0 index 1000 error. Furthermore, if someone could
please lead a helping hand it would be much appreciated. I know this must
seem very trivial, but it isn't for me. At the moment I think implementing
this from scratch or with an array would have been much easier.
Thanks Mike
|
Priority queues in linear structures tend to need random access, so I
can see LinkedList making it very difficult. Why use it?
If you are using 1.5 or later, why not java.util.PriorityQueue?
If you cannot use the 1.5 implementation, have you considered a TreeSet,
with comparison based on the priority? The highest priority item will
always be its first() or last(), depending on the comparison direction.
Patricia |
|
| Back to top |
|
|
Guest
|
| Posted: Thu Nov 23, 2006 2:38 am Post subject: Re: Priority Queue implemented as LinkedList api class java |
|
|
Michael wrote (11/13/06):
| Quote: | [snip]
However, by using the LinkedList class, I am almost certain I have to |
use an iterator to step through all entries in the PQ and return
the
one with the minimum key.
[snip]
Using a LinkedList might make some sense, IMO, for this assignment.
My approach would be to wrap the queued objects into something that
holds both the object and its priority number:
class PriorityWrapper {
int priority = 0;
Object queuedObj = null;
public PriorityWrapper( Object obj, int priority) {
//...
}
}
Now in building the LinkedList, fill it with these "wrappers", so queued
objects can be inserted in order of priority. The insert() method becomes
the fun part. I wrote one that just iterates over the list from
highest to lowest priority (lowest to highest priority number) until
the right spot is reached. Then list.add(int index, Object o) does the
insertion.
Would/should one use a Comparator here? Or is that just for purists?
Also, does anyone find other impurities in this approach to Michael's
post?
TonyD |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
