在相同优先级的情况下维持PriorityQueue插入顺序 [英] Maintaining PriorityQueue insertion order incase of equal priority

问题描述

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

I am using a priorityQueue to implement BFS. I want to maintain the insertion order in the case of equal priority while inserting and also after poping.

我重写了equals方法，如下所示，插入顺序保持了插入时的预期效果.

I overrode the equals method as shown below and the insertion order is maintained as expected while inserting.

但是，一旦我执行删除或投票，元素的顺序会改变.

But, once I do a remove or poll, the order of the elements changes.

即使在民意测验中，如何保持插入顺序?

How can I maintain the insertion order even on poll?

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].

In the code snippet above, I expect pq to be [1 , 2 , 3].

推荐答案

通常，优先级队列不会根据到达时间对等优先级项目进行排序.如果要这样做，则需要创建自己的比较函数，该函数不仅比较优先级值，而且还比较到达时间(或者也许单调增加的序列号).这里的关键是优先级队列本身并不关心插入顺序.

In general, priority queues do not order equal-priority items based on arrival time. If you want to do that, you need to create your own comparison function that compares not only the priority value but also the arrival time (or perhaps a monotonically increasing sequence number). The key here is that the priority queue itself doesn't care about insertion order.

您需要调用此PriorityQueue构造函数，提供您自己的 Comparator .

You need to call this PriorityQueue constructor, supplying your own Comparator.

如果您对为什么基于堆的优先级队列无法强制执行所需的顺序感兴趣，请参见 https://stackoverflow.com/a/54916335/56778 .

If you're interested in why a heap-based priority queue can't force the ordering you want, see https://stackoverflow.com/a/54916335/56778.

这篇关于在相同优先级的情况下维持PriorityQueue插入顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！