五、教材翻译
Translation
Chapter 9 Priority Queue
＊第九章 优先队列
9.1 The Priority Queue Abstract Data Type
＊9.1 节 优先队列抽象数据结构
9.1.1 Priorities
＊优先级
In Chapter 6, we introduced the queue ADT as a collection of
objects that are added and removed according to the first-in,
first-out (FIFO) principle. A company’s customer call center
embodies such a model in which waiting customers are told
“calls will be answered in the order that they were received.” In
that setting, a new call is added to the back of the queue, and
each time a customer service representative becomes available,
he or she is connected with the call that is removed from the front
of the call queue.
＊在第 6 章中，我们介绍了先进先出的队列 ADT。公司的
客户呼叫中心体现了这样一种模式，其中等待客户被告知
“ 呼叫将按照接收到的顺序进行回复” 。在该设置中，新呼
叫被添加到队列的后面，每次客户服务变得可用时，队列
最前面的等待者也将从呼叫队列的前面移除。
In practice, there are many applications in which a queue-
like structure is used to manage objects that must be processed
in some way, but for which the first-in, first-out policy does not
suffice. Consider, for example, an air-traffic control center that
has to decide which flight to clear for landing from among many
approaching the airport. This choice may be influenced by
factors such as each plane’s distance from the runway, time
spent waiting in a holding pattern, or amount of remaining fuel.
It is unlikely that the landing decisions are based purely on a
FIFO policy.
＊实际上，有许多应用程序使用队列式结构来管理对象，
但是有的时候先进先出的策略并不太合适。例如，一个空
中交通管制中心，必须决定在许多接近机场的飞机中，哪
些飞机应该最先着陆。这种选择可能受到诸如每个飞机与
跑道的距离，等待在持有模式中花费的时间或剩余燃料量
等因素的影响。着陆决定不太可能纯粹基于 FIFO 策略。
There are other situations in which a “first come, first serve”
policy might seem reasonable, yet for which other priorities
come into play. To use another airline analogy, suppose a certain
flight is fully booked an hour prior to departure. Be- cause of the
possibility of cancellations, the airline maintains a queue of
standby passengers hoping to get a seat. Although the priority of
a standby passenger is influenced by the check-in time of that
passenger, other considerations include the fare paid and
frequent-flyer status. So it may be that an available seat is given
to a passenger who has arrived later than another, if such a
passenger is assigned a better priority by the airline agent.
＊
In this chapter, we introduce a new abstract data type known
as a priority queue. This is a collection of prioritized elements
that allows arbitrary element insertion, and allows the removal
of the element that has first priority. When an element is added
to a priority queue, the user designates its priority by providing
an associated key. The element with the minimum key will be the
next to be removed from the queue (thus, an element with key 1
will be given priority over an element with key 2). Although it
is quite common for priorities to be expressed numerically, any
Python object may be used as a key, as long as the object type
supports a consistent meaning for the test a < b, for any instances
a and b, so as to define a natural order of the keys. With such
generality, applications may develop their own notion of priority
for each element. For example, different financial analysts may
assign different ratings (i.e., priorities) to a particular asset, such
as a share of stock.
＊
评论0