如何配置Java优先队列以忽略重复项？

Question

我认为add()应该忽略重复的元素，但我的输出结果中有重复项。我应该如何避免存储重复项？

我还想知道优先队列是如何检查两个元素是否重复的。我猜它使用比较器equals来比较，但我想要确保。

谢谢

- sgarg

Answer 1

这里是从PriorityQueue Javadoc中的一部分：

此队列根据在构建时指定的顺序对元素进行排序，该顺序根据它们的自然顺序（参见Comparable）或根据比较器指定，具体取决于使用哪个构造函数来指定。

因此，如果您将Comparator指定为构造函数参数，则PriorityQueue使用Comparator，否则使用compareTo(...)方法（元素必须实现Comparable接口）。

PriorityQueue允许重复项。因此，如果您想避免这种情况，则需要实现自己的Queue版本。您可以在"Effective Java", page 85中找到非常优雅的方法。或者，您可以扩展PriorityQueue类并覆盖add方法（这是放置contains(...)检查的完美位置）。

- Sebastian Łaskawiec

---

使用继承PriorityQueue类还是使用包装器放置唯一元素哪个更好？ - Gaurav

Answer 2

在Java中，PriorityQueue不对重复元素有任何限制。如果您想确保两个相同的元素从未同时存在于优先队列中，则最简单的方法是与优先队列并行维护一个单独的Set。每次要将元素插入到优先队列中时，可以检查集合是否已包含它，如果没有，则将其添加到集合和优先队列中。每当您从优先队列中删除一个元素时，也要从集合中删除该元素。

或者，根据您打算在优先队列上执行哪些操作以及在您的情况下如何定义相等性，可以考虑使用单个TreeSet来替换优先队列。这样做仍然可以执行所有重要操作，并且还不允许重复。

- Jiddo

---

可以说明为什么有人不会使用TreeSet。（在TreeSet中执行peek操作的时间复杂度是O(logn)，而在PriorityQueue中是常数级别；从TreeSet中弹出头部的成本略高于PriorityQueue。） - JMess

Answer 3

以下是示例实现。

import java.util.PriorityQueue;

public class NoDuplicates<E> extends PriorityQueue<E> 
{
    @Override
    public boolean offer(E e) 
    {
        boolean isAdded = false;
        if(!super.contains(e))
        {
            isAdded = super.offer(e);
        }
        return isAdded;
    }
    public static void main(String args[])
    {
        PriorityQueue<Integer> p = new NoDuplicates<Integer>();
        p.add(10);
        p.add(20);
        p.add(10);
        for(int i =0;i<=2;i++)
        {
            System.out.println(p.poll());
        }
        
    }
}

导致

10
20
null

这表明它不会添加重复元素10。

- Raghava

---

考虑到PriorityQueue是一个二叉堆，而其contains()方法的时间复杂度为O(n)，我很难想象还有比这段代码更低效的东西了。 - devoured elysium

Answer 4

集合是唯一可以忽略重复项的数据结构。列表和队列不具备这个特性。（LinkedList 是一个队列）

如果你想去除重复项，可以检查你使用 take() 方法获取的条目是否与前一个相同，如果相同则忽略它。你可以按照任何方式进行比较。 ;)

- Peter Lawrey

---

为了使其正常工作，比较函数应该与相等性一致，但这并不总是情况。例如，多状态A*搜索中，开放状态Q在权重上进行比较，在节点上进行相等性比较，这两者之间没有关联。 - Laurent Grégoire

@LaurentGrégoire，你可以构造这样的情况，但是考虑到compareTo的javadoc声明它应该与equals一致，不这样做是相当严重的hack。 - Peter Lawrey

Answer 5

重写方法hashCode()和equals(Object obj)以避免重复，并使用方法contains来检查对象是否存在。

class Element {
    int i, j, distance;
    public Element(int i, int j, int distance) {
        super();
        this.i = i;
        this.j = j;
        this.distance = distance;
    }
    @Override
    public int hashCode() {
        return Objects.hash(i, j);
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        
        Element element = (Element) obj;
        return Objects.equals(i, element.i) && Objects.equals(j, element.j) ;
    }
    @Override
    public String toString() {
        return "Element [i=" + i + ", j=" + j + ", distance=" + distance + "]";
    }
}

请查看以下内容

PriorityQueue<Element> pq = new PriorityQueue<>((a, b) ->  (a.distance == b.distance ?  a.i == b.i ? a.j - b.j : a.i - b.i : a.distance - b.distance));
pq.add(new Element(i1, j1, d1)); // element values

Element e2 = new Element(i2, j2, d2);
if(!pq.contains(e2)) {
    pq.add(e2);
}

- Anurag