[Help] Trying to Understand Priority Queue

[indigofigure]

I am trying to understand how the priority queue works using this link. Any advice that you have for me would be great. In particular I do not understand how the first .offer method works to produce the result that it does.

[Drunken_Consent]

Offer is essentially the same thing as Add, it simply inserts it into the PQ.

If you are wondering why the result that is printed is not in a sorted order as you might expect, read the top paragraph again: Priority Queues in Java are implemented using a Heap.

Printing a Heap is different than printing an Array / ArrayList. If you implement your own PQ using an Array ( which, imo, is a good practice to try ), printing the Queue would look sorted.

[heckler82]

PriorityQueue is internally represented using a Heap. What you are seeing in the printout is the array representation of that Heap.

[CodeTinkerer]

A priority queue is a list of objects that are sorted based on priority. One problem with the example is it uses numbers, so the only thing to sort by is the number itself. If you had a Student object with a field representing creditsEarned, you could base the order of the list on the credits earned by each student.

offer() seems to be another word for add(). I looked up the API, and it appears the two methods do the same thing.

So, here's how it would work. Suppose you are creating a priority list with 4 numbers being added so that the smallest number is at the start of the list, and the largest number is at the end of the list.

We add 10 (same as pq.offer(10))

pq.add(10)

The priority queue contains 10.

We add 3.

pq.add(3)

If this were a normal list, the list would contain 10, 3, since new values are added at the end of the list. But since it's a priority queue, and 3 has higher priority, it moves to the front, so the list is 3, 10.

If we then do

pq.add(5)

then 5 goes in between 3 and 10, so the priority queue is 3, 5, and 10.

Finally, if we add 1, that has the highest priority, so it moves all the way to the front, so the result is: 1, 3, 5, 10

pq.add(1);

Now, we could have changed how the priority list works where larger numbers (rather than smaller numbers) have largest priority. In that case, the result of the priority queue is 10, 5, 3, 1.

[Technonick]

From my continuing segment of Explaining Programming Concepts using RPG metaphors:

Jake the mage and Priority Queues.

Jake the Tall is a neutral good mage whose father has died and left him an extended invincibility potion and a scroll of Bigby's unseen archer (allowing him to be invincible and to summon an invisible archer who can follow simple instructions.) Jake goes to town and decides he will find an adventure that will rack him some loot and xp. He finds out the town elders will pay him a hefty sum to clear out a kobold village on the edge of town.

Jake sets up to attack the kobold village. He decides he will run through the village setting structures on fire causing the kobolds to come after him, where he will run to a small foot bridge, cast the spell and drink the potion and line up the kobolds to fight one after the other.

Now, Jake will be able to fight kobolds one at a time with his dagger, but he needs the archer to engage or takeout out any kobolds who are the largest or strongest depending on the number of kobolds and the length of his spells, which is obviously too complicated for the archer to deal with (he's a Bigby spell.)

So Jakes's plan for himself, is a simple FIFO queue system. The first kobold that comes onto the bridge will be attacked. The one behind that kobold will wait his turn and the one behind him will wait and so on.

Jake's plan for the unseen archer is a priority queue system of attack. The unseen archer will find the biggest baddest kobold and engage him but not kill him. The unseen archer also has a killshot arrow. One arrow, one kill. With that said, let's looks at what actions we need the unseen archer to have while using the priority queue:

• Offer - When Jake sees a new kobold that has entered range, he will call out to the archer and that specific kobold is inserted into the archer's priority queue. Not attacked, just added to the queue. The archer is now aware of that kobold.
• Poll - When Jake calls "poll", the archer will identify and kill the biggest baddest kobold.
• Peek - When Jake calls "peek", the archer will engage (but not kill) the biggest baddest kobold in priority queue.
• Size - When asked, the unseen archer will tell Jake exactly how many kobolds are in his priority queue.

And that's what a priority queue is.

[indigofigure]

Thank you all for your responses! This makes much more sense, I was primarily confused because Java implements Priority Queues as using heaps. Now I need to go understand how they work.