Implementing Priority queue using hashmap

Question

This may be a very naive question or does not make sense. But i am really confused about implementation of priority queue. Why we cannot use a hashmap with key as priority and value as the data with that priority. Am i missing some basic here. For eg: If priority of A is 1, B is 3 and c is 4 we can simply keep 1,3,4 as keys and A,B,C as values of hashmap respectively for priority queue implementation. Please clear my logic

Answer 1

The problem with that implementation is that it doesn't take advantage of the HashMap capabilities to easily access any element given the key. Since you are making a queue, you won't have the priorities 1, 3, 4 later, and will just need to find the highest priority of the map, having to iterate it entirely to do so!

A map works something like this: it creates a gigantic array with null values in all positions (very, vey big). Then, it uses a formula to take your key, normally a string or a string representation and turn that into a number. A simple way to do this would be to sum the char codes of each letter, though that is a bad choice for the map, you can look it up why later. Then, it caps that number with modulus (remainder) size of the array (e.g., n % size in Java), so that it becomes a valid position in the array, and then put the element there. That way, it is very easy to make intensive search, because you don't need to search, you know exactly where each element is.

Therefore, implementing a queue with a Map would be very memory intensive, without the clear advantage of the HashMap search. Furthermore, iterating over it is very, very expensive, because you need to iterate over a gigantic array and ignore the null values; you are not sure where the actual values are. Imagine in your example, that the priorities go from 0 to 100. Even though you would never have 100 tasks, you would have a 100 position array to iterate over, checking on each position if there is a task with that priority.

A better way would be to use a simple list and store the priority within the data. Assuming that the priority doesn't change over time, you will just need to iterate once upon adding, to find the correct place, and always access the first (or last) element, the one with known highest priority.

On a final note o performance, it is better to iterate upon adding, even though you are adding the exact same amount of time that you are searching. Because when you search for the highest priority, you need to go until the end, every time, because maybe the last element is the bigger one. Note that the HashMap won't store your items organized in neat crescent order, even if your keys are numeric Strings or Integer. It is designed specially not to do that, to avoid conflicts (two similar objects having the same key, and thus requiring the need to add a list to that particular position of the big array). When you add, however, assuming your list is already ordered, you just need to iterate until you reach the correct destination.

Answer 2

When you try to iterate through the HashMap, you're going to get a strange order. HashMaps (or any maps for that matter) have no guaranteed traversal order, so you won't be able to "order" the queue in an efficient manner.

You could of course query all keys, order that list, and get values in order, but that's very inefficient compared to the alternatives (you're already at O(n^2) for the length of the keys without doing additional work)

Answer 3

Long story short, it all comes down to the fact that HashMaps aren't ordered, so you'll end up needing some external mechanism anyways to figure out what's "next" in the queue.

So for example, say you put in the entries

[1, "A"]
[3, "B"]
[4, "C"]

If you only have a HashMap, there's no reliable way of figuring out that 1 is "first" short of iterating through every key, because internally the keys could be:

[1, "A"]
[3, "B"]
[4, "C"]

or

[3, "B"]
[4, "C"]
[1, "A"]

or

[3, "B"]
[1, "A"]
[4, "C"]

and so on.

From the HashMap javadoc:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

So using a HashMap really doesn't make sense because the extra work you'd have to do anyways makes a HashMap less efficient than a heap in the end.

---

Now, if you really wanted to use a HashMap, you could:

• Grab the EntrySet, sort by key, then get the first value. It's OK if that is the only time you need to grab the first value, but that is rarely the case. As soon as you alter the map and need to do it again, the efficiency is worse than a regular heap.

• Use some external mechanism, such as an ArrayList or something to keep track of the keys, perhaps keeping it sorted as part of inserting values. At this point might as well skip the HashMap and implement the heap "normally", though, because otherwise you're basically doing the same thing but with the added complication of splitting your data between an ArrayList and HashMap.

So in the end, the extra work isn't really worth it.

Answer 4

A priorityQueue keeps your data sorted and maintains that structure, if you were to iterate thru the priorityQueue, it will return your data in the way you implemented its constructor, consistently. A HashMap does not preserve insertion order. If you tried to return all elements from your hashmap, you will get inconsistent results.

Aside from that, priorityQueue uses a min/max heap to keep your data ordered, therefore, any insertion/deletion is Log(n) as it has to compare nodes from log(n) levels to maintain the priorityQueue property. where n is the number of data in the queue.

perhaps what you could use is a linkedHashMap to preserve the order of your data as it uses a doubly linkedList struture. However, the runtime is worse than that of the priortyQueue for crucial operations such as getMax(). A priorityQueue will do it in O(log(n)) time whereas a linkedHashMap would take O(n) time as now you must iterate thru the entire linkedList to find the max/min values.

Hope that helps

Answer 5

The purpose of Priority Queues is to be able to access the element of highest priority the quickest and the purpose of the HashMap is to allow you to map keys to values and so therefore access those elements in O(1) Time Complexity.

The O(1) Time Complexity comes from the Hash function that calculates the key or "index" in the HashMap for any input. However combining the hash function and the priority queue becomes complicated due to the fact that the HashMap assigns keys according to the hash function, but the priority queue assigns the keys according to the priority of elements, so when combined, disagree with each other.

Answer 6

The issue I'm seeing here is that implementing priority queue with hashmap will forbid the existance of two elements with the same priority, say A-3 and C-3 will both have key 3. The might be circumvented if you have some other data structure I suppose, but with the original hashmap this can be an issue.