Mastering Algorithms with C

Priority Queue Example: Parcel Sorting

Most delivery services offer several options for how fast a parcel can be delivered. Generally, the more a person is willing to pay, the faster the parcel is guaranteed to arrive. Since large delivery services handle millions of parcels each day, prioritizing parcels during the sorting process is important. This is especially true when space associated with a delivery mechanism becomes limited. In this case, parcels with the highest priority must go first. For example, if an airplane is making only one more trip for the day back to a central hub from a busy metropolitan area, all parcels requiring delivery the next day had better be on board.

One way to ensure that parcels heading to a certain destination are processed according to the correct prioritization is to store information about them in a priority queue. The sorting process begins by scanning parcels into the system. As each parcel is scanned, its information is prioritized in the queue so that when parcels begin to move through the system, those with the highest priority will go first.

Example 10.4 presents two functions, get_ parcel and put_ parcel, both of which operate on a priority queue containing parcel records of type Parcel. Parcel is defined in parcel.h, which is not shown. A sorter calls put_ parcel to load information about a parcel into the system. One member of the Parcel structure passed to put_ parcel is a priority code. The put_ parcel function inserts a parcel into ...