Java中的优先队列

Question

Java中的优先队列

javapriority-queue

3

你能有两个参数吗？比如，我想添加一个字符串和相应的整数到一个优先键中。然后我将按照该整数对其进行排序。我知道如何添加字符串或整数，但不知道如何同时添加两者。请问有谁能指点我一下，让我知道是否正确地处理了这个问题？

- Shonna

4个回答

4

这里有一种通用的方法来实现它：

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

}

- sandves

3

如何创建一个包含这两个字段（int和String）的新类，然后实现Comparable（在int字段上进行比较）。不要忘记还要覆盖hashCode()和equals()方法（请参阅Comparable类的javadoc以了解覆盖这些方法的原因）。

这是你想要的吗？

- Neeme Praks

请问您能否讨论一下为什么他应该重写equals()（然后相应地重写hashCode()）？我本以为实现Comparable就足够了。 - Catchwa

请查看Comparable类的Javadoc，了解为什么要重写equals()和hashCode()方法。 - NamshubWriter

我的回答已经更新，并附上了JavaDoc的参考。 - Neeme Praks

@NamshubWriter，你能看一下我在这个问题中使用PriorityQueue的方式吗？http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 - committedandroider

2

如果您想使用多个元素作为键，可以创建一个封装它们的类，并将该类型用作键。同样适用于值。您应该使这个自定义键类实现 Comparable 接口, 并重写您创建的自定义键类的equals()和hashCode()方法。

- Michael Aaron Safyan

你能否看一下我在这个问题中使用PriorityQueue的方式？http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 - committedandroider

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NamshubWriter · Accepted Answer

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

第一种解决方案是让此数据对象实现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构造函数。在这种情况下，Data不需要实现Comparable；您只需要一个定义排序的Comparator：

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