java - Java中的优先级队列

Question

你可以有2个参数吗？例如，我想将一个字符串和一个相应的整数添加到优先级键中。然后我将按该整数对其进行排序。我知道如何添加字符串或整数，但我不知道如何添加两者。有人可以指出我正确的方向，让我知道我是否以正确的方式去做这件事？

Answer 1

有两种方法可以做到这一点。无论哪种方式，您都希望创建一个自定义对象，该对象同时包含字符串（您想要的值）和整数（优先级）。

第一个解决方案是让这个数据对象实现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()
}

然后当你这样做

PriorityQueue<Data> queue = new PriorityQueue<Data>();

队列将按照方法定义的顺序对项目进行排序compareTo。

此解决方案的问题在于，如果您希望仅对整数进行排序，那么任何equals一种方法和您的compareTo方法都将不一致，或者您的equals方法将不正确。

更好的解决方案是使用带有Comparator的PriorityQueue构造函数。在这种情况下，不必实施; 您只需要一个定义您的订购的：DataComparableComparator

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

请注意，由于此比较器不获取数据，因此我将其设为单例。

然后，您可以这样创建队列行：

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

如何创建一个包含这两个字段（和）的新类，然后实现Comparable（在 int 字段上进行比较）。不要忘记也重写and （参见Comparable类 javadoc 以了解重写这些方法的原因）。intStringhashCode()equals()

这就是你所追求的吗？

Answer 4

如果要使用多个元素作为键，可以创建一个封装两者的类，然后使用该类型作为键。价值观也是如此。您应该为您创建的自定义键类创建此自定义键类Comparable、覆盖equals()和覆盖hashCode()。