What is a priority queue and what is it useful for

When we code and use a priority queue, what exactly does priority stand for? Is it something abstract or is it something concrete, such as sorting per height of different buildings?
What is the advantage of using a priority queue?

3 Answers
3

A plain queue deals with items on a first-come-first-served basis. Priority queues determine a service order based on the priorities of the items. With a priority queue the next item to be dealt with will be the one with the highest priority ranking.

Examples:

This is something concrete, it determines the actual operations of a system. Your job as a programmer is to identify and reflect that real-world behavior by supplying an ordering property. In Java this is done by making the objects Comparable or supplying a Comparator.

Comparable

Comparator

You can define the priority by letting the elements implement Comparable interface and offering a Comparator to construct the queue, see the doc:

Comparable

Comparator

The elements of the priority queue are ordered according to their
natural ordering, or by a Comparator provided at queue construction
time.

taking into consideration that one of the constructor accepts a Comparator... it gets obvious compared on what. By default, unless specified, it uses Comparator.naturalOrder()

Comparator

Comparator.naturalOrder()

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.