How do I increment value of an entry if it already exists in the PQ?

Question

I'm using this question as a starting point:

Add Key and Value into an Priority Queue and Sort by Key in Java

I have a similar situation, where I have a PQ of my POJO that has two important attributes: key and value.

However, before I add a new entry into the PQ, first I want to check if an entry with the same key exists already in the PQ. In that case, I want to increment its value instead. How do I go about doing this?

I think when PQ.contains(entry) is true you will have to get an iterator and iterate on the queue and update when you find a match. If not you can use Map + PQ, whenever you add entry to PQ add the same into Map too. So you can do lookup on Map and then if you update Entry it is updated in PQ too. — Ajay, Mar 12 '18 at 00:34
For PQ to maintain max heap I think you need to remove old Entry and add the update Entry. — Ajay, Mar 12 '18 at 00:40
Please do not vandalize your question so as to invalidate existing answers! — Martin James, Mar 12 '18 at 07:14
You cannot use an old question to ask a new one, please leave the question as it was, if my answer was helpful mark it as accepted, and the new question you have you can post it, you'll problably have an answer. — Jose Da Silva Gomes, Mar 12 '18 at 21:03
That what you are asking I already said it is not possible, you cannot have a priority queue ordered by priority, identified by some key and then modify the value which the pq is ordered by, the queue won't get ordered right. You can use the map like i said below, and use the pq instead TreeSet, just replace TreeSet with PriorityQueue... And consume the values with `remove()`. — Jose Da Silva Gomes, Mar 12 '18 at 21:33

score 1 · Answer 1 · edited Jun 20 '20 at 09:12

The javadoc says that.

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))

But again, this is not necessary. What it is necessary is to override the method public boolean equals(Object entry) for the method contains() to work, instead you are declaring the method public boolean equals(Entry entry).

You should have an equals() similar to.

@Override
public boolean equals(Object entry) {
    if (entry instanceof Entry) return this.key == ((Entry) entry).key;
    else return false;
}

Another thing to consider it that it is a terrible idea to mutate the object when this is already in a sorted/hashed collection. This will cause strange behavior. I'll show you an example.

Using this a toString() method in your entry.

@Override
public String toString() {
    return String.format("{ %d, %d }", key, value);
}

Using this code to print the priority queue.

PriorityQueue<Entry> queue = new PriorityQueue<>();
for (Entry data : entries) {
    Entry entry = new Entry(data.getKey(), data.getValue());
    if (queue.contains(entry)) {
        for (Entry current : queue) { // just for the example
            if (current.equals(entry)) {
                current.addToValue(entry.getValue());
            }
        }
    } else {
        queue.add(entry);
    }
}

while (!queue.isEmpty()) // print ordered
    System.out.println(queue.poll());

With this data.

List<Entry> entries = Arrays.asList(
        new Entry(1, 4),
        new Entry(2, 3),
        new Entry(2, 5)
);

The output is not correctly sorted { 1, 4 }, { 2, 8 } instead { 2, 8 }, { 1, 4 }, this because the entry with id 2 was mutated after it was added to the collection.

By the other hand, with this data

List<Entry> entries = Arrays.asList(
        new Entry(1, 4),
        new Entry(2, 8)
);

It prints the output correctly sorted { 2, 8 }, { 1, 4 }.

The solution could be using a HashMap and then a TreeSet.

Map<Integer, Integer> map = new HashMap<>();
for (Entry data : entries) { // here instead read from csv and create entry
    map.computeIfPresent(data.getKey(), (k, v) -> v + data.getValue()); // sum priorities
    map.putIfAbsent(data.getKey(), data.getValue()); // add when not exists
}

Now that you have a map identified by the key and containing the sumarized values of the priorities, you can use a TreeSet or a PriorityQueue to sort the entries.

You don't need to use your custom Entry, you can use the java Entry and pass a Comparator to the TreeSet / PriorityQueue.

TreeSet<Map.Entry<Integer, Integer>> treeSet = new TreeSet<>((e1, e2) ->
        e2.getValue() - e1.getValue() != 0 ?
        e2.getValue() - e1.getValue() :
        e2.getKey() - e1.getKey());
treeSet.addAll(map.entrySet());
System.out.println(treeSet);

This comparator compares first the priority, if is different, return -1 or 1, following a descendant order.

If the priority is the same, it compares the key, and returns -1 or 1 (0 is not possible because there are not duplicate keys) and order of the keys is descending.

How do I increment value of an entry if it already exists in the PQ?

1 Answers1