Priority Queue in Java

Question

Do you have 2 options? for example, I want to add a string and the corresponding integer to the priority key. Then I'm going to sort it by this whole. I know how to add a string or an integer, but I do not know how to add both. Can someone please point me in the right direction and let me know if I even go this right way?

Answer 1

There are two ways to do this. In any case, you want to create a custom object that contains both String (the value you want) and an integer (priority).

The first solution is to implement this Comparable data object :

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 the elements in the order determined by the method compareTo.

The problem with this solution is that if you want the order to be only on an integer, then the method equalsand your method compareTowill not be consistent, or your method equalswill be wrong.

A better solution would be to use the PriorityQueue constructor , which accepts a Comparator . In this case Data, it would not be necessary to implement Comparable; you just need Comparatorone that defines your order:

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 does not accept data, I made it single.

:

PriorityQueue<Data> queue = new PriorityQueue<Data>(
    initialCapacity, OrderDataByPrority.INSTANCE);

Answer 2

:

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;
            }
    }

}

Answer 3

, (int String), Comparable ( int). hashCode() equals() (. Comparable javadoc ).

, ?

Answer 4

If you want to use multiple elements as a key, you can create a class that encapsulates both, and then use this type as a key. Similarly for values. You must make this custom key class Comparable, override equals()and override hashCode()for the custom key class you are creating.