Hi! I am trying to implement a comparator to sort Integers in a priorityqueue. I've looked at many examples, but i cant think of why the following code doesnt sort integers in increasing/decreasing order.
the output is:
Is there something missing? Any help would be appreciated!
Welcome to the ranch Grace. Do you know what is a PriorityQueue? Do you know how it works? Read this first. I don't think you need a comparator at all to sort primitive types when you add them to a PriorityQueue. The implementation of the class is such that it should do it by itself for you. Read the description of the class carefully. The answer to why it is printing the stored integers randomly is given there.
Joined: Mar 31, 2013
Yup, I roughly know what a priority queue is. I suppose its just a normal queue with items sorted according to a specific priority. However, the implementation boggles me.
Basically my problem is like this: I have an Word object, that consists of an (int number) and a (double weight), i didnt put it in the code cos it might mix things up..
This Word object was what I wanted to sort with the priority queue, not the Integer object. The (int number) of the Word object is what i would like to use to sort these objects within the queue, and i thought i would need an comparator for this, since it isn't a primitive and Java might have trouble sorting it via its "natural order" (correct me if wrong). But i couldn't even get the basic case as illustrated in the code above correct. Hence I'd like to know why it may be not working.
Grace wrote: ....But i couldn't even get the basic case as illustrated in the code above correct. Hence I'd like to know why it may be not working.
So let us go step by step and not get ahead of ourselves. Why do you think it is printing the numbers in random order when the very definition of a PriorityQueue says that it sorts the elements according to their natural ordering or according to a comparator depending on the constructor being used. Did you read the whole description of the class in the link I provided? No. Hecn you missed this line:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Internally, the queue has actually stored the elements in their natural order. It just won't print them in that order unless you call the Arrays.sort(array ) method explicitly. This is baffling to me too. But it is how the class is designed.
Joined: Mar 31, 2013
Hmm... yeah i guess when I was reading it the dots didnt connect (Iterator=array?), and partly because i didnt think Arrays.sort would work on an object..
But anyway, thanks for the explanation! I realized after using poll(), that the queue is sorted afterall, just not when I converted it to an array... took me long enough >:\
No. An iterator is not the same as an array. An iterator is simply a pointer that is used to traverse any collection of objects. The point is that when you traverse through the elements of a PriorityQueue, you may not see any sort order, although the queue sorts it internally. It's like you give me 10 cards with random numbers from 1 to 100. Now I know which is the largest and which is the smallest. I know the order. When you ask me for the largest, I shall give that card to you. But when you ask me to show you all the cards at once, I will simply show them to you in any random order. I have sorted them in my mind. That's how a PriorityQueue works.
subject: Using a comparator to sort a priority queue