CODEWITHSUNDEEP
javaalgorithmdata-structures
jials
jials

Reputation: 13

How to maintain the precedence of an object inside a priority queue once it is being taken out to update its priority?

I am wondering if there is anyway to maintain the precedence of an object inside a priority queue once it is being removed and reinserted into the queue to update its priority?

The way I do this is that I remove the object from the priority queue and put the updated object into the queue again. However, this will disrupt the natural ordering I had implemented using Comparator

The Comparator:

class PriorityValueComparator implements Comparator<Human>{
    public int compare(Human x, Human y){
        return y._priority - x._priority;
    }
}

For example,

insert in the following order: John, Alex, Kerby, Jane

The priority queue is in the following form: [Jane, 100], [Kerby, 59], [Alex, 33], [John, 13]

Update John to 100

[John, 100] (since John is inserted before Jane), [Jane, 100], [Kerby, 59], [Alex, 33]

UPDATE: Alternatively, in the Human Class, a static attribute time can be added. Inside the constructor of Human,

public Human() {
    //add in whatever you want here
    time++; //This will ensure that every elements will have their own unique order number
}

Upvotes: 1

Views: 102

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

The priority queue implementation is allowed to choose arbitrarily between elements with the same priority. If you want to force a particular order, then you need to change the comparator. Assuming that you maintain a field _insertion_time such that humans inserted earlier have lesser, nonnegative values, then you can rewrite the comparator to

class PriorityValueComparator implements Comparator<Human>{
    public int compare(Human x, Human y){
        if (y._priority != x._priority) return y._priority - x._priority;
        else return y._insertion_time - x._insertion_time;
    }
}

Upvotes: 1

Related Questions