What is a priority queue and what is it useful for

Question

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?

Answer 1

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:

• Airlines board "first class" customers before "economy class"
• Hospital emergency rooms deal with heart attacks, hemorrhaging, and breathing problems before looking at other patients
• Many restaurants will seat VIPs before regular customers, even if the latter have reservations.

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.

Answer 2

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

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