priority queue

[Navhpf]

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

 

[Thomas Kreiss]

Hi!

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

Regards,
Thomas

 

[Joona I Palaste]

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 ([email protected]) ------------- 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

 

[Navhpf]

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