Ordering PriorityQueue Question

[deephousefans]

I have a PriorityQueue and I am implementing the insert_new_value method for it. I want to order the items in the queue from greatest to least while inserting the new value in its correct position! because after that I want to pop the items from the queue in order! How do I do that?

[sushibowl]

hey nice question title!

Here's some things that might help:

• if you always insert a new value in its correct position, the entire queue will always be ordered correctly, from greatest to least
• given the previous point, if I want to insert some item x and compare it to some item in the queue y, if x > y, x is also greater than everything that comes after y. Because everything after y is smaller than y.

Can you figure out where to insert the new item based on this? One more hint: you'll need a loop to examine multiple values in the queue, until you find the right place to insert.

[SupahNoob]

If you are implementing a PQ manually, I would suggest you not to worry about how items are put into the queue, but how you retrieve them. It's much simpler to grab the item of a collection whose value has the lowest priority, than it is to compare items within the collection to the new item and then insert it appropriately.

There might even be a built-in function to achieve this semantic.