|
Having the right priorities is important to succeeding in life. On a quiet Saturday afternoon, presented with the opportunity of taking a nap, watching TV, playing soccer, or studying this chapter, the zealous student will certainly give first priority to the latter task. Outside of comfortable campus boundaries, priorities are an even more serious matter. Consider, for example, an air-traffic control center that has to decide which flight to clear for landing from among many approaching the airport. The priority of a flight may depend not only on the plane's distance from the runway, but also on the amount of fuel it has left. Choosing the next flight to land may be a life-critical decision. Another example is a standby passenger who, when she checks in, is told by the gate agent that she is `first' in line for a fully-booked flight. Thus, she thinks she has top priority if seats become available. Little does she know that the airline will give first priority to a standby passenger who has arrived later, if such a passenger is given a better priority by the agent (priority here is measured in terms of the fare paid, frequent-flyer status, and check-in time). In this chapter, we study data structures that store `prioritized elements,' that is, elements that have priorities assigned to them. Such a priority is typically a numerical value, and we take the view that the smallest numerical value should have first priority. However, as we show in this chapter, we can support the opposite viewpoint just as easily. More generally, priorities can be viewed as arbitrary objects, so long as there is a consistent way of comparing pairs of such objects to see if one is less than or equal to the other. This general viewpoint allows us to define a fairly generic ADT for storing prioritized elements. A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority; that is, the element with first priority can be removed at any time. This ADT is fundamentally different from the position-based data structures we discussed in previous chapters, such as stacks, queues, deques, sequences, and even trees. These other data structures store elements at specific positions, which are often positions in a linear arrangement of the elements determined by the insertion and deletion operations performed. The priority queue ADT stores elements according to their priorities, and has no notion of `position.' We present the priority queue ADT in this chapter, giving two implementations of a priority queue using sequences. These implementations are simple, but unfortunately not very efficient. Even so, they allow us to easily describe two well-known sorting algorithms, insertion-sort and selection-sort. We follow this presentation by giving a more efficient implementation of a priority queue, based on a concrete data structure known as a heap. A heap uses the hierarchical power of binary trees to support the priority queue operations in logarithmic time, which leads to a fast sorting algorithm known as heap-sort. We conclude this chapter with a discussion of a design pattern known as the locator. |