Priority Queue using MultiMap - Java

Question

Hi. I have to implement Priority Queue using MultiMap. I use MultiMap from Google Collections. The following code creates a MultiMap and adds few elements into 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 the pop method?

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

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

Answer 1

If I'm understanding correctly that you're using Multimap as the internals for your own PriorityQueue class, rather than just trying to use Multimap as a priority queue, then you should probably keep a SortedSet (I'll call it sortedKeys) of all the keys. Then you can use multimap.get(sortedKeys.first()) to pop the first element.

By "keeping a SortedSet", I mean that each time you add something to your Multimap, add its key to a SortedSet. When you remove items from your Multimap, remove their keys from the SortedSet. The goal being that your SortedSet stays equal to Multimap.keySet(), but without the overhead of calling SortedSet.clear(); SortedSet.addAll(...) all the time.

The alternative is going to be creating a SortedSet each time which would be much slower. It may help you understand what I'm saying though:

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

Answer 2

The HashMultimap you're using won't give you any help in efficiently selecting the lowest element. Instead use a TreeMultimap (also in Google Collections) which lets you specify an ordering and iterate through the items in the list in that order. For instance:

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

You'll notice that this always prints out entries in priority order, so to get the first-priority element you can just do multimap.entries().iterator().next() (assuming you know the map has at least one element).

See the TreeMultimap documentation for more information.

Answer 3

Could you simply use the PriorityQueue class in the JDK?

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

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