1

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
}
5
  • 2
    I don't understand the purpose of this. If you're updating its priority, why do you want to leave it at its old priority? Sep 10, 2014 at 1:18
  • Because he is actually the first one to enter this priority queue and I would like to maintain that order when it is updated. I am just wondering if this can be done.
    – jials
    Sep 10, 2014 at 1:31
  • So you want insertion order on top of the heap behavior? Sep 10, 2014 at 1:36
  • @jials Your question doesn't make sense. The priority is determined by the comparator. If you change it, you change it. There aren't two priorities. If you want to make insertion order part of the comparison, use it as a minor key in your comparator, if you can find a way to maintain it.
    – user207421
    Sep 10, 2014 at 1:57
  • @Delimanolis Yep. That's the thing I'm trying to implement
    – jials
    Sep 10, 2014 at 4:01

1 Answer 1

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.