Maintaining PriorityQueue insertion order incase of equal priority

Question

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.

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

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

It looks like you create a new cell every time you insert it into the priority queue. Could you add a timestamp to the Cell class and use that in the `equals` and `compareTo` methods? That would allow you to track when cells are added provided that you always create them when inserting. — kingkupps, Sep 11 '19 at 18:22
@kingkupps Yes, I think that will work. But, I am looking for a way without changing my class structure. — Mounika, Sep 12 '19 at 05:21

score 4 · Accepted Answer · answered Sep 11 '19 at 22:35

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.

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

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.

Maintaining PriorityQueue insertion order incase of equal priority

1 Answers1

Linked