Priority Queue Using MultiMap - Java

Question

I need to implement Priority Queue using MultiMap. I am using MultiMap from Google Collections. The following code creates a MultiMap and adds several elements to it.

Multimap<Integer, String> multimap = HashMultimap.create(); multimap.put(5,"example"); multimap.put(1,"is"); multimap.put(1,"this"); multimap.put(4,"some"); 

Now my problem is how to write a pop method?

I think there should be a for loop and it should be repeated through MultiMap.

The lowest key should be the highest priority, so in C ++ I would set the pointer to the first element and increment it. How to do it in Java?

Answer 1

HashMultimap that you use will not give you any help in effectively selecting the lowest element. Instead, use TreeMultimap (also in Google Collections), which allows you to specify the order and iterate the items in the list in that order. For example:

 for (Map.Entry<Integer, String> entry : multimap.entries()) { System.out.println("Item " + entry.getValue() + " has priority " + entry.getKey(); } 

You will notice that this always prints the entries in order of priority, so to get the first priority element, you can simply do multimap.entries().iterator().next() (if you know that the map has at least one element).

See the TreeMultimap documentation for more details .

Answer 2

If I understand correctly that you are using Multimap as internal elements for your own PriorityQueue class, and not just trying to use Multimap as a priority queue, then you should probably keep the SortedSet (I'll call it sortedKeys) of all the keys. Then you can use multimap.get(sortedKeys.first()) to open the first item.

By “saving a SortedSet,” I mean that every time you add something to your Multimap, add its key to the SortedSet. When you delete items from your Multimap, remove their keys from the SortedSet. The goal is to keep your SortedSet equal to Multimap.keySet (), but without the overhead of calling SortedSet.clear(); SortedSet.addAll(...) SortedSet.clear(); SortedSet.addAll(...) all the time.

An alternative would be to create a SortedSet every time, which will be much slower. This may help you understand what I am saying:

 public Collection<V> pop() { SortedSet keys = new TreeSet(multimap.keySet()); return multimap.get(keys.first()); } 

Answer 3

Could you just use the PriorityQueue class in the JDK?

With the suggested TreeMultimap method suggested by jacobm, the following code is more concise.

 Iterator<String> iterator = multimap.values().iterator(); String value = iterator.next(); iterator.remove();