Chapter 4. Priority queues

Table of Contents

4.1. Priority queues with unbounded priorities (class p_queue)
4.2. Priority queues with bounded integral priorities (class b_priority_queue)

The early bird catches the worm.” We got to know this principle in Section 2.7 when we talked about queues. In an ordinary queue, things are stored ordered by the time of their insertion; they are taken out of the queue in this order again (FIFO principle). Often, however, one wants to store things ordered by a priority different from the entry time, and take them out again according to this ordering. Then, between two things with different priority p1 and p2, a new thing may have to be inserted, with a priority p' in between p1 and p2 - in contrast to an ordinary queue, in which insertions can be carried out at the end only.

In daily life, for example, there are very urgent, “normally” urgent and less urgent tasks, which must be finished in the order of their urgency (priority).The most urgent task is always to be finished next. Finishing a task, however, may create new tasks to be finished, with priorities of their own. Moreover, the priority of a task absolutely may change before the task was finished if this task is suddenly classified as important or less important because of outer circumstances.

What is needed for the modeling of such problem definitions is a priority queue. This is a data structure that allows to store information, ordered by a certain priority, and to take out the information with the lowest priority.

[Warning]Warning

According to the classic definition of a priority queue, which also the corresponding types of LEDA follow, the information with the lowest priority value is considered the most important one. Therefore the smaller the value, the higher the (colloquial) priority of an information. Due to this fact, always the information with the lowest priority value is taken out of the queue next, not the one with the highest priority!

The classic definition requires in addition that the priority of an information can be reduced by an arbitrary value.[38]

An illustrative example of a priority queue is the casualty unit in a large hospital: When a new patient arrives, the severity of its injury or illness is valued; according to this severity, he is inserted into a priority queue. (With a classic priority queue used, the priority value is the smaller, the more severe the injury or the illness is.) The worst case, for example a heart attack, is always treated next. But now, the treatment of a case can create new cases: By mistake, a needle may have been rammed into the eye of the heart attack patient during his treatment. This still has to be treated urgently, but it is no longer highly dangerous. And the hot temperature of the patient who has just returned home from a tropics journey may suddenly decline: By this, the priority of its case decreases. (With a classic priority queue, this means that the corresponding priority value is increased.) In reality, the private patients always have the lowest priority value.

Priority queues are an important algorithmic ingredient in discrete event simulation: Events shall be handled whose points in time, when written down on the time axis, do not show any simple pattern so that they cannot be created by a simple loop. Here it is not possible to implement the management of the points in time as we did in our simulation of the queues at the Saarbrücken Central Station. There we simply run through all minutes of a year, which is not inefficient, because on an average, some events actually do occur in every minute. There we did not implement an explicit management of the points in time, though: The for loop iterates by itself over all points in time of the time period considered. If, in contrast, the events occurred only every couple of hours and irregularly, then this way of performing the simulation would be a waste of computing time, because an event actually would occur (and had to be handled) in a few loops only. Here it would be advantageous to manage the events in a priority queue, ordered by their points in time, with the priorities corresponding to the points in time, and to jump only from point in time to point in time by successively extracting the event with the lowest priority.

Other typical application areas of priority queues are algorithms for computing shortest paths in graphs (in which the edges carry a distance information), algorithms for computing maximum flows in network graphs (in which the edges carry a capacity information), coding algorithms, compression algorithms, and branch-and-bound algorithms for solving optimization problems.

For this kind of problems, LEDA offers the classes p_queue and b_priority_queue. The former class implements priority queues for information with arbitrary priority type. (This type has to be a linearly ordered one, of course.) The latter class offers an especially efficient implementation for priorities that are known a priori to be integer numbers and to originate from an interval not too large.



[38] The classic definition does not require that a priority can also be increased. This has historical reasons that relate to the efficiency of good implementations.




Imprint-Dataprotection