在优先级相同的情况下维护优先级队列插入顺序

Question

我正在使用 priorityQueue 来实现 BFS。我想在插入时和弹出后在同等优先级的情况下保持插入顺序。

我覆盖了 equals 方法，如下所示，插入时插入顺序按预期保持不变。

但是，一旦我进行删除或轮询，元素的顺序发生变化。

如何在轮询时保持插入顺序？

class Cell implements Comparable<Cell>{
    int v;
    int dis;
    public Cell(int v, int dis) {
        this.v = v;
        this.dis = dis;
    }

    public int compareTo(Cell c2) {
        if((this.dis > c2.dis)) {
            return 1;
        } else if(this.dis < c2.dis) {
            return -1;
        } 
        return 0;
    }

    public boolean equals(Object o) {
        if(!(o instanceof Cell)) {
            return false;
        }
        Cell c = (Cell) o;
        if(this.dis == c.dis) {
            return true;
        } 
        return false;
    }

    public String toString() {
        return v+" ";
    }

}


    PriorityQueue<Cell> pq = new PriorityQueue<Cell>();

    pq.offer(new Cell(0,0));
    vis[0] = true;

    while(!pq.isEmpty()) {
        Cell c = pq.peek();
        int adj;
        //let's suppose getAdjVertex method will return 1,2,3
        while((adj = getAdjVertex(c.v,list.get(c.v),vis)) != -1) {
            vis[adj] = true;
            pq.offer(new Cell(adj, c.dis+1));
        }

        System.out.println("pq1 = " + pq); //Here the order is correct
        //pq1 = [0 , 1 , 2 , 3 ]
        pq.remove(c);
        System.out.println("pq = " + pq); // Here the order is changed
        //pq = [3 , 1 , 2 ]
    }

在上面的代码片段中，我希望 pq 为 [1 , 2 , 3].

Answer 1

一般来说，优先级队列不会根据到达时间对同等优先级的项目进行排序。如果你想这样做，你需要创建你自己的比较函数，它不仅比较优先级值而且比较到达时间（或者可能是单调递增的序列号）。这里的关键是优先级队列本身并不关心插入顺序。

您需要调用 this PriorityQueue constructor，提供您自己的 Comparator。

如果您对为什么基于堆的优先级队列不能强制执行您想要的顺序感兴趣，请参阅。

在优先级相同的情况下维护优先级队列插入顺序

Maintaining PriorityQueue insertion order incase of equal priority

java

equals

priority-queue