Priority Queue in Java
Solution 1
There are two ways to do this. Either way, you want to create a custom object that holds both the String (the value you want) and the integer (the priority).
The first solution is to have this data object implement Comparable:
class Data implements Comparable<Data> {
private final String message;
private final int priority;
public Data(String message, int priority) {
this.message = message;
this.priority = priority;
}
@Override
int compareTo(Data other) {
return Integer.valueOf(priority).compareTo(other.priority);
}
// also implement equals() and hashCode()
}
Then when you do
PriorityQueue<Data> queue = new PriorityQueue<Data>();
the queue will order items by the order defined by the compareTo
method.
The problem with this solution is that if you want the ordering to be only on the integer, then either equals
method and your compareTo
method will not be consistent or your equals
method will not be correct.
A better solution would be to use the PriorityQueue constructor that takes a Comparator. In this case, Data
wouldn't have to implement Comparable
; you just need a Comparator
that defines your ordering:
public final class OrderDataByPriority implements Comparator<Data> {
public static final OrderDataByPriority INSTANCE = new OrderDataByPriority();
private OrderDataByPriority() {}
@Override
public int compare(Data data1, Data data2) {
return Integer.valueOf(data1.priority).compareTo(data2.priority);
}
@Override
public boolean equals(Object other) {
return other == OrderDataByInteger.INSTANCE;
}
private Object readResolve() {
return INSTANCE;
}
}
Note that since this comparator takes no data, I made it a singleton.
You can then create the queue line this:
PriorityQueue<Data> queue = new PriorityQueue<Data>(
initialCapacity, OrderDataByPrority.INSTANCE);
Solution 2
Here is a generic way of doing it:
public class PriorityQueue<T> {
private java.util.PriorityQueue<IntPriorityComparableWrapper<T>> queue;
public PriorityQueue() {
queue = new java.util.PriorityQueue<IntPriorityComparableWrapper<T>>();
}
public void add( int priority, T object ) {
queue.add( new IntPriorityComparableWrapper<T>(object, priority) );
}
public T get() {
return (null != queue.peek())? queue.poll().getObject() : null;
}
/**
* A "wrapper" to impose comparable properties on any object placed in the
* queue.
*/
private static class IntPriorityComparableWrapper<T>
implements Comparable<IntPriorityComparableWrapper<T>> {
private T object;
private int priority;
public IntPriorityComparableWrapper( T object, int priority ) {
this.object = object;
this.priority = priority;
}
public int compareTo( IntPriorityComparableWrapper<T> anotherObject ) {
return this.priority - anotherObject.priority;
}
public int getPriority() {
return priority;
}
public T getObject() {
return object;
}
}
}
Solution 3
How about creating a new class that contains those two fields (int
and String
) and then implementing Comparable (comparing on the int field). Don't forget to override also hashCode()
and equals()
(see the Comparable class javadoc for reasoning behind overriding these methods).
Is that what you are after?
Solution 4
If you want to use multiple elements as a key, you can create a class that encapsulates both, and then use that type as the key. Likewise for the values. You should make this custom key class Comparable
, override equals()
, and override hashCode()
for the custom key class that you create.
Shonna
Updated on June 04, 2022Comments
-
Shonna about 2 years
can you have 2 parameters? for instance, i want to add a string and a corresponding integer to a priority key. Then I am going to sort it by that integer. I know how to add either a string or a integer, but I dont know how to add both. Can someone please point me in the right direction and let me know if i am even going about this the right way?
-
Catchwa over 13 yearsCan you please discuss why he should override
equals()
(and then consequentlyhashCode()
)? I would have thought that implementingComparable
would have been sufficient. -
NamshubWriter over 13 yearsSee the class Javadoc for Comparable for why you want to override equals() and hashCode()
-
Shonna over 13 yearsi am using BUfferedReader to read the input from users.. so they put in the message, then hit enter, then put in the integer(priorty)... now when i do queue.add("string") .. but i need to add them both.. how would i do that?
-
Shonna over 13 yearsi am going to be printing out the strings in descending order.. but its the integer that i will be using to do the comparison... so the integer will need to be connected to the string they entered someway
-
NamshubWriter over 13 yearsYou would do queue.add(new Data(message, priority));
-
NamshubWriter over 13 yearsI updated the answer to make it clearer that the integer is a priority and to recommend using Comparator instead of Comparable. Good luck!
-
Neeme Praks over 13 yearsUpdated my answer with reference to JavaDoc
-
committedandroider over 9 yearsCan you take a look at my use of a PriorityQueue in this question? stackoverflow.com/questions/28800287/…
-
committedandroider over 9 years@NamshubWriter Can you take a look at my use of PriorityQueue in this question? stackoverflow.com/questions/28800287/…