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
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.