Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > priority queue

Reply
Thread Tools

priority queue

 
 
Navhpf
Guest
Posts: n/a
 
      02-23-2004
Hi all!

I would need a kind of data structure that I cannot find in the JAVA
API.
It is a priority queue, allowing duplicates on the keys, but not on
the elements.
The kind of keys I need are of type float, and the elements would be 2
or 3-dimensional integer arrays.
As I understood it, Maps would not allow duplicate keys, and I cannot
figure how to build an ordering of the data I use to build a Set (any
Comparable implementation I can think of is not compatible with
equals() ).

Any help greatly appreciated,

NaV
 
Reply With Quote
 
 
 
 
Thomas Kreiss
Guest
Posts: n/a
 
      02-23-2004
Hi!

I use the BinaryHeap from http://jakarta.apache.org/commons/collections/
for this cases.

Regards,
Thomas

> Hi all!
>
> I would need a kind of data structure that I cannot find in the JAVA
> API.
> It is a priority queue, allowing duplicates on the keys, but not on
> the elements.
> The kind of keys I need are of type float, and the elements would be 2
> or 3-dimensional integer arrays.
> As I understood it, Maps would not allow duplicate keys, and I cannot
> figure how to build an ordering of the data I use to build a Set (any
> Comparable implementation I can think of is not compatible with
> equals() ).
>
> Any help greatly appreciated,
>
> NaV



 
Reply With Quote
 
 
 
 
Joona I Palaste
Guest
Posts: n/a
 
      02-23-2004
Navhpf <(E-Mail Removed)> scribbled the following:
> Hi all!


> I would need a kind of data structure that I cannot find in the JAVA
> API.
> It is a priority queue, allowing duplicates on the keys, but not on
> the elements.
> The kind of keys I need are of type float, and the elements would be 2
> or 3-dimensional integer arrays.
> As I understood it, Maps would not allow duplicate keys, and I cannot
> figure how to build an ordering of the data I use to build a Set (any
> Comparable implementation I can think of is not compatible with
> equals() ).


> Any help greatly appreciated,


If I'm not altogether wrong, a priority queue which doesn't allow
changing priorities while the object is still in the queue, can be made
with several queues, one for each priority.
Adding a new element takes O(1) time: put it in the queue that
corresponds to its priority.
Removing an element takes O(n) time: remove an element from the
highest-priority queue you find having any elements left.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"'It can be easily shown that' means 'I saw a proof of this once (which I didn't
understand) which I can no longer remember'."
- A maths teacher
 
Reply With Quote
 
Navhpf
Guest
Posts: n/a
 
      02-23-2004
I currently use the JDSL ArrayHeap, but I can't figure out how to
check for the presence of an element in the queue in an efficient way
(I do it by fetching an iterator over all the Queue elements).
This check is needed, as the JDSL PriorityQueue does not check for
duplicated elements.

Thanks for your answers, more input is welcome

NaV
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
efficient priority queue for a few descrete priority levels Marcel Müller C++ 3 04-27-2009 03:22 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM
Should I use shutter-priority or appurature-priority? ½ Confused Digital Photography 4 02-22-2006 09:48 AM
Question about Aperture priority and Shutter Priority John Edwards Digital Photography 8 01-05-2005 04:58 PM



Advertisments