priority queue

[sara]

I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:

PriorityQueue<Vector<Integer>> pq = new PriorityQueue<Vector<Integer>>
(new PriorityQueueComparator());

where PriorityQueueComparator is a comparator defined by myself.
I want to find the top element of pq, say t and remove any element of
t from other vectors. For example for the following pq:
pq={[1,2,3], [2,3],[3,4]}
I want to any element of [1,2,3] from other member of pq, i.e., [2,5],
[3,4]. Therefore, pq should become pq={[1,2,3],[4],[]}. The problem is
when I use Iterator to iterate over pq members and update them, the
priority of the members based on their size are not kept. In other
words, for this example, pq={[1,2,3],[],[4]} instead of {[1,2,3],[4],
[]}. Is there anyway to update members of pq and update it accordingly?

 

[John B. Matthews]

I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:

PriorityQueue<Vector<Integer>> pq = new PriorityQueue<Vector<Integer>>
(new PriorityQueueComparator());

where PriorityQueueComparator is a comparator defined by myself. I
want to find the top element of pq, say t and remove any element of t
from other vectors. For example for the following pq: pq={[1,2,3],
[2,3],[3,4]} I want to [?] any element of [1,2,3] from other member
of pq, i.e., [2,5], [3,4]. Therefore, pq should become
pq={[1,2,3],[4],[]}. The problem is when I use Iterator to iterate
over pq members and update them, the priority of the members based on
their size are not kept. In other words, for this example,
pq={[1,2,3],[],[4]} instead of {[1,2,3],[4], []}. Is there anyway to
update members of pq and update it accordingly?

I'm having trouble understanding your goal, but the API mentions
Arrays.sort() in this context: "The Iterator provided in method
iterator() is not guaranteed to traverse the elements of the priority
queue in any particular order. If you need ordered traversal, consider
using Arrays.sort(pq.toArray())."

<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>

An <http://pscode.org/sscce.html> might clarify the question.

 

[sara]

Thanks but it does not answer my question. I defined the priority such
that the priority of an element p is higher than q if p has more
members than q (p and q are both vectors). I want to remove some
elements of p. If I do it using iterators, the priority is messed up.

I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:

PriorityQueue<Vector<Integer>> pq = new PriorityQueue<Vector<Integer>>
(new PriorityQueueComparator());

where PriorityQueueComparator is a comparator defined by myself. I
want to find the top element of pq, say t and remove any element of t
from other vectors. For example for the following pq: pq={[1,2,3],
[2,3],[3,4]} I want to [?] any element of [1,2,3] from other member
of pq, i.e., [2,5], [3,4]. Therefore, pq should become
pq={[1,2,3],[4],[]}. The problem is when I use Iterator to iterate
over pq members and update them, the priority of the members based on
their size are not kept. In other words, for this example,
pq={[1,2,3],[],[4]} instead of {[1,2,3],[4], []}. Is there anyway to
update members of pq and update it accordingly?

I'm having trouble understanding your goal, but the API mentions
Arrays.sort() in this context: "The Iterator provided in method
iterator() is not guaranteed to traverse the elements of the priority
queue in any particular order. If you need ordered traversal, consider
using Arrays.sort(pq.toArray())."

<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>

An <http://pscode.org/sscce.html> might clarify the question.

 

[John B. Matthews]

I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:

PriorityQueue<Vector<Integer>> pq = new PriorityQueue<Vector<Integer>>
(new PriorityQueueComparator());

where PriorityQueueComparator is a comparator defined by myself.
I want to find the top element of pq, say t and remove any
element of t from other vectors. For example for the following
pq: pq={[1,2,3], [2,3],[3,4]} I want to [?] any element of
[1,2,3] from other member of pq, i.e., [2,5], [3,4]. Therefore,
pq should become pq={[1,2,3],[4],[]}. The problem is when I use
Iterator to iterate over pq members and update them, the priority
of the members based on their size are not kept. In other words,
for this example, pq={[1,2,3],[],[4]} instead of {[1,2,3],[4],
[]}. Is there anyway to update members of pq and update it
accordingly?

I'm having trouble understanding your goal, but the API mentions
Arrays.sort() in this context: "The Iterator provided in method
iterator() is not guaranteed to traverse the elements of the
priority queue in any particular order. If you need ordered
traversal, consider using Arrays.sort(pq.toArray())."

<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>

An <http://pscode.org/sscce.html> might clarify the question.

Thanks but it does not answer my question. I defined the priority
such that the priority of an element p is higher than q if p has more
members than q (p and q are both vectors). I want to remove some
elements of p. If I do it using iterators, the priority is messed up.

Indeed, the API addresses this limitation directly in the passage I
quoted above. Perhaps you can use your Comparator in Arrays.sort() to
achieve thew desired effect.

[Please do not top-post; please trim signatures.]

 

[Andreas Leitgeb]

The obvious solution is to remove and add each changed item.
That would mess up iterating over the queue, so I would keep a separate
set containing the same items, ...

for(Vector<Integer> v : setOfVectors){
if(v != headVector){

Good advice - an identical Vector could have been added twice.
By the way: it is better to replace "Vector" by "ArrayList"!

if(v.removeAll(headVector){
pq.remove(v);
pq.add(v);

Removing and adding an element is quite inefficient with priority queues:
removing means replacing the element by the last one and rolling that
back down to re-establish the heap-properties, and adding means appending
the new element at the end and rolling it up till the heap is fine.

Last time I had to do immediately subsequent remove&add operation, I
copied the PriorityQueue-source into my own package, and added a
replace-method, that would add the new element at the spot of the old
one and from there on roll it into its final place.

Back then I also posted this here, but no one seemed interested.

Furthermore, it surely pays to watch the vector's length before and
after the .removeAll(...) and do the re-queueing only if it really
changed.

The remove call is linear time,

The linear component is, so I guess, searching for the item, so if
you get to do your own PQ, you could iterate the internal array, and
save the effort of searching each element.

Besides, I wonder, if the PQ's iterator supports removing and adding
elements without a concurrent modification exception. Is there a
general rule about iterator.add(...) in sorted Collections (i.e. where
the new element is likely added somewhere else than at the iterator
position)?

Are you sure a PriorityQueue is the right solution for something this
dynamic? I would consider e.g. an ArrayList that gets sorted after each
block of changes.

Very good advice. Even with all the tricks and a handcrafted PQ, you won't
get any better than O(n*log(n)) (assuming each vector's length is bounded),
which can also be expected from sorted ArrayList.

 

[sara]

Good advice - an identical Vector could have been added twice.
By the way: it is better to replace "Vector" by "ArrayList"!


Removing and adding an element is quite inefficient with priority queues:
  removing means replacing the element by the last one and rolling that
  back down to re-establish the heap-properties, and adding means appending
  the new element at the end and rolling it up till the heap is fine.

Last time I had to do immediately subsequent remove&add operation, I
copied the PriorityQueue-source into my own package, and added a
replace-method, that would add the new element at the spot of the old
one and from there on roll it into its final place.

Back then I also posted this here, but no one seemed interested.

Furthermore, it surely pays to watch the vector's length before and
after the .removeAll(...) and do the re-queueing only if it really
changed.


The linear component is, so I guess, searching for the item, so if
you get to do your own PQ, you could iterate the internal array, and
save the effort of searching each element.

Besides, I wonder, if the PQ's iterator supports removing and adding
elements without a concurrent modification exception.  Is there a
general rule about iterator.add(...) in sorted Collections (i.e. where
the new element is likely added somewhere else than at the iterator
position)?


Very good advice. Even with all the tricks and a handcrafted PQ, you won't
get any better than  O(n*log(n)) (assuming each vector's length is bounded),
which can also be expected from sorted ArrayList.

Thanks a lot but how can I implement priority queue using ArrayList?
Also, my main goal is to implement greedy set cover algorithm fast and
therefore I am trying to use a priority queue. Thanks.

 

[Andreas Leitgeb]

Thanks a lot but how can I implement priority queue using ArrayList?
Also, my main goal is to implement greedy set cover algorithm fast and
therefore I am trying to use a priority queue. Thanks.

The point is, that a PriorityQueue is only then efficient, if the
elements added do not change lateron. But this is not in your case:
with each element that you remove, you end up modifying possibly *all*
the other elements, so a PriorityQueue is just the wrong tool for this
task.

The algorithm for removal then goes like this:
pick the first element into a variable "head".
iterate the ArrayList:
if (current element == head) continue;
(current element).removeAll(head)
end of iteration
sort the ArrayList according to element's size.

As it seems, sorting an ArrayList is a bit awkward, in that
you have to copy the contents to an array first, sort that,
and then bring the array back into an ArrayList, but I may
have missed something there.

 

[Guest]

I want to create a PriorityQueue pq which contains vectors of integers
and the priority is based on the size of the vector representing each
member. The declaration is as following:

PriorityQueue<Vector<Integer>> pq = new PriorityQueue<Vector<Integer>>
(new PriorityQueueComparator());

where PriorityQueueComparator is a comparator defined by myself.
I want to find the top element of pq, say t and remove any element of
t from other vectors. For example for the following pq:
pq={[1,2,3], [2,3],[3,4]}
I want to any element of [1,2,3] from other member of pq, i.e., [2,5],
[3,4]. Therefore, pq should become pq={[1,2,3],[4],[]}. The problem is
when I use Iterator to iterate over pq members and update them, the
priority of the members based on their size are not kept. In other
words, for this example, pq={[1,2,3],[],[4]} instead of {[1,2,3],[4],
[]}. Is there anyway to update members of pq and update it accordingly?

Others have been attempting to work with you on the solution.
I would like to take a different tack.
Why do you need this functionality?
What is the underlying problem that you are trying to solve?

Perhaps there is a better way to tackle the problem.

Bill

 

[Lew]

if (current element == head) continue;

Be careful of the difference between '==' and '.equals()'.

 

[Steve Wampler]

The point is, that a PriorityQueue is only then efficient, if the
elements added do not change lateron. But this is not in your case:
with each element that you remove, you end up modifying possibly *all*
the other elements, so a PriorityQueue is just the wrong tool for this
task.

I'm wondering why the PriorityQueue has to be an ArrayList - there are
certainly 'better' data structures for implementing a PQ [a Heap comes
to mind...]. Just because Java doesn't supply a Heap in any of the
standard packages doesn't mean that it's not a better approach than
building a PQ from an ArrayList - which has so many of the disadvantages
Andreas and others have given. And there may well be better ways
than building a PQ using a Heap - I haven't looked at PQ implementations
in a long time.

So I'm not sure you should give up on the PQ, but consider more efficient
ways to implement it than relying directly using a data structure supplied
by Sun.

 

[Andreas Leitgeb]

Be careful of the difference between '==' and '.equals()'.

Indeed, and "==" was carefully chosen here. But it was good
to point out, since pseudocode isn't always that exact

 

[Andreas Leitgeb]

Thanks a lot but how can I implement priority queue using ArrayList?
Also, my main goal is to implement greedy set cover algorithm fast and
therefore I am trying to use a priority queue. Thanks.
The point is, that a PriorityQueue is only then efficient, if the
elements added do not change lateron. But this is not in your case:
with each element that you remove, you end up modifying possibly *all*
the other elements, so a PriorityQueue is just the wrong tool for this
task.

I'm wondering why the PriorityQueue has to be an ArrayList - there are
certainly 'better' data structures for implementing a PQ [a Heap comes
to mind...].

Where did you get the impression from, that PQ had anything to do with AL?

The java.util.PriorityQueue implementation looks like a heap
implementation to me, and the first comment inside its class body says
"Priority queue represented as a balanced binary heap: the two children
of queue[n] are queue[2*n+1] and queue[2*(n+1)].". Priority changes
could be made more efficient if the implementation provided a method to
do it directly.

That would be the "replace" operation I mentioned.

Normally, the merit of a PQ is finding a succession of head items
without having to scan the entire contents each time. In this case, the
OP intends scanning the entire set of nodes each time a head item is
removed, in order to subtract out the old head node's elements. The same
scan could determine the new largest subset.

So, by dropping this vague requirement of any particular ordering in
the structure, we get from O(n*log(n)) down to O(n). Cool!

 

[Steve Wampler]

Where did you get the impression from, that PQ had anything to do with AL?

From my misreading of the OP's question about how to implement an PQ with an AL.
Maybe someday I'll mature enough to read all the way through a thread
before commenting!

 

[Tom Anderson]

As it seems, sorting an ArrayList is a bit awkward, in that you have to
copy the contents to an array first, sort that, and then bring the array
back into an ArrayList, but I may have missed something there.

You may have missed this:

http://java.sun.com/javase/6/docs/a...ml#sort(java.util.List, java.util.Comparator)

tom

 

[Tom Anderson]

Good advice - an identical Vector could have been added twice.
By the way: it is better to replace "Vector" by "ArrayList"!


Removing and adding an element is quite inefficient with priority queues:
removing means replacing the element by the last one and rolling that
back down to re-establish the heap-properties, and adding means appending
the new element at the end and rolling it up till the heap is fine.

True. Another way of doing this would be to do the removes in the for loop
(using Iterator.remove()), and then accumulate vectors to be re-added in a
side list; after the for loop, do an addAll to put the side list back into
the priority queue. My assumptions there are that (a) Iterator.remove() is
more efficient than PriorityQueue.remove() and (b) the addAll is more
efficient than a series of adds, although both of those are aspirations
rather than certainties.

This would also avoid the need to have the set which is a copy of the
priority list.

That explanation isn't very clear, so here's some code:

PriorityQueue<List<Integer>> pq;

Iterator<List<Integer>> it = pq.iterator();
List<Integer> head = pq.poll();
Collection<List<Integer>> toBeReAdded = new ArrayList<List<Integer>>();
while (it.hasNext()) {
List<Integer> vec = it.next();
if (vec.removeAll(head)) {
it.remove();
toBeReAdded.add(vec);
}
}
pq.addAll(toBeReAdded);

I wonder if there's an even cleverer approach using bitsets and/or an
inverted index, though.

Last time I had to do immediately subsequent remove&add operation, I
copied the PriorityQueue-source into my own package, and added a
replace-method, that would add the new element at the spot of the old
one and from there on roll it into its final place.

Back then I also posted this here, but no one seemed interested.

Awww, poor Andreas!

I'm thinking about starting a home for stray datastructures, such as my
GettableHashSet:

http://urchin.earth.li/~twic/GettableSet/

To be joined by the TreeList (O(log n) remove()!) i'm currently very
slowly working on. Maybe it can go there.

Furthermore, it surely pays to watch the vector's length before and
after the .removeAll(...) and do the re-queueing only if it really
changed.

That's why Patricia is making the remove/add predicate on the return value
of removeAll - removeAll returns true if the list was changed by the call,
and false if it wasn't.

Besides, I wonder, if the PQ's iterator supports removing and adding
elements without a concurrent modification exception. Is there a
general rule about iterator.add(...) in sorted Collections (i.e. where
the new element is likely added somewhere else than at the iterator
position)?

The decision about when to throw a ConcurrentModificationException is left
to the concrete class, rather than being specified in the collection
interface. PriorityQueue's iterator() method says:

Returns an iterator over the elements in this queue. The iterator does
not return the elements in any particular order.

Which means that this isn't a sorted collection in the sense you mean, but
says nothing about there being or not being any fail-fast behaviour.

tom

 

[Tom Anderson]

... which says, in part:

This implementation dumps the specified list into an array,
sorts the array, and iterates over the list resetting each
element from the corresponding position in the array.

That's pretty much the awkward operation Andreas described.

DOH! I had this idea that for lists which implemented RandomAccess, it was
done in-place. But of course, the sort is a mergesort, which is impossible
to implement in-place anyway, and would be a real pain to implement
half-in-place.

The Javadoc goes on to say:

This avoids the n^2 log(n) performance that would result from
attempting to sort a linked list in place.

... which is an admission of a drawback of the Holy Principles of
Encapsulation and Information Hiding. If the Collections class could
directly manipulate the links of a LinkedList, the sort could be done in
O(n lg(n)) time, in-place and without creating additional garbage. The
copy-sort-restore dance is not required by the inherent complexity of
the sorting problem, but by a limitation imposed by adherence to OO
purity.

Well, that and the decision to put sort in Collections rather than List.

(Of course, even an OO purist might have allowed sort() and other
utilities as methods of List itself instead of packaging them in a
separate Collections class.

Exactly.

I think the whole Collections class is a festering pile of code stink -
almost all its methods belong somewhere else. Yes, putting them in List
would mean that every implementation would have to implement them, but
there could be general-purpose implementations in AbstractList (maybe
accessible as static methods for the benefit of lists which don't extend
AbstractList), so it wouldn't impose on most implementations.

But if you pursue *that* stratagem too far, you wind up with enormous
SwissArmyKnife classes ...)

So don't pursue it too far!

tom