PriorityQueue, insert with priority

Question

I'd like to know how can I add a value to a PriorityQueue with a specific value.

I have a Map<Integer, Integer> // element -> value and I'd like to insert elements to the PriorityQueue with the value priority.

For example:

Map{1=0, 3=5265, 5=22375, 7=4202, 9=233, 11=351, 13=119}

should have this order in the Queue:

{1, 13, 9, 11, 7, 3, 5}

You can insert the `Map.Entry`s in the `PriorityQueue` and provide a `Comparator` of these. Or create your own `Pair` type with the priority and value with an associated `Comparator`. — Sotirios Delimanolis, Mar 31 '15 at 23:11
possible duplicate of [Java: How do I use a PriorityQueue?](http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue) — Stefan Falk, Mar 31 '15 at 23:11
@SotiriosDelimanolis I have no idea how that should be done. — vixero, Mar 31 '15 at 23:14

John Kugelman · Accepted Answer · 2015-03-31T23:23:37.773

PriorityQueue expects elements to be comparable to each other. It doesn't explicitly track the priority of each element itself. It just compares them to each other. That means you'll need to the elements and their priorities into the queue in pairs.

One way to do that is to add Map.Entrys directly and create the queue with a custom comparator.

PriorityQueue<Map.Entry<Integer, Integer>> queue =
    new PriorityQueue<>(Comparator.comparing(entry -> entry.getValue()));

queue.addAll(map.entrySet());

Another way would be to create a simple class holding both values that implements Comparable. Something like:

class ElementPriority implements Comparable<ElementPriority> {
    int element;
    int priority;

    @Override public int compareTo(ElementPriority other) {
        return Integer.compare(this.priority, other.priority);
    }
}

Or if you want to get really hacky you could combine each pair of ints into a long holding both values. If you store the priorities in the big end then the elements should naturally sort by priority.

PriorityQueue<Long> queue = new PriorityQueue<>();

map.forEach((element, priority) -> {
    queue.add((priority & 0xFFFFFFFFL) << 32 | (element & 0xFFFFFFFFL));
});

This is highly dubious, but hey, what the heck.

I'm still a bit confused. The 1st method give me a cast error. I think i'll try the 2nd one. — vixero, Mar 31 '15 at 23:24

PriorityQueue, insert with priority

1 Answers1