Good question. So if you have access to a priority queue natively or through some library, in practice you should use that if you want this kind of behavior. In the real world you’ll rarely need to recreate basic data structure classes like this.

But in an interview, or just as an exercise you may be asked to implement certain things from scratch. So it’s good to know how they work under the hood, and that’s why I included them here.

And just to be clear, because I remember this being a question that came up frequently in class, you can think of a priority queue as something with a kind of behavior. It’s like a normal queue, but the highest priority thing in it, always moves up to the front. This priority could be measured by the size of an integer, alphabetical order or any other way of ranking elements.

This behavior can be implemented in various ways. You could use an array, a linked list, a set… as long as the behavior works as intended, it will be a priority queue.

Now, which data structure you use is an important choice because of time and space complexity. Heaps are a good data structure for priority queues because you always have access to the top element in constant time, and because the rest of the data is in a semi-sorted state, you can re-establish a valid heap in logarithmic time.

This is great for a system where you are adding and removing a lot of elements from a priority queue.

Hope this answers your question!