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 the priority queue, which prioritizes the parcel among
the others. When the sorter is ready to move the next parcel through
the system, it calls get_ parcel. The
get_ parcel function fetches the parcel with the
next-highest priority so that parcels are processed in the correct
order.
A priority queue is a good way to manage parcels because at any moment, we are interested only in the parcel with the next highest priority. Therefore, we can avoid the overhead of keeping parcels completely sorted. The runtime complexities of get_ parcel and put_ parcel are both O (lg n) because the two functions simply call pqueue_extract and pqueue_insert respectively, which are both O (lg n) operations.
/***************************************************************************** * * * ------------------------------- parcels.c ------------------------------ * * * *****************************************************************************/ #include <stdlib.h> #include <string.h> #include "parcel.h" #include "parcels.h" #include "pqueue.h" /***************************************************************************** * * * ------------------------------ get_parcel ------------------------------ * * * *****************************************************************************/ int get_parcel(PQueue *parcels, Parcel *parcel) { Parcel *data; if (pqueue_size(parcels) == 0) /************************************************************************** * * * Return that there are no parcels. * * * **************************************************************************/ return -1; else { if (pqueue_extract(parcels, (void **)&data) != 0) /*********************************************************************** * * * Return that a parcel could not be retrieved. * * * ***********************************************************************/ return -1; else { /*********************************************************************** * * * Pass back the highest-priority parcel. * * * ***********************************************************************/ memcpy(parcel, data, sizeof(Parcel)); free(data); } } return 0; } /***************************************************************************** * * * ------------------------------ put_parcel ------------------------------ * * * *****************************************************************************/ int put_parcel(PQueue *parcels, const Parcel *parcel) { Parcel *data; /***************************************************************************** * * * Allocate storage for the parcel. * * * *****************************************************************************/ if ((data = (Parcel *)malloc(sizeof(Parcel))) == NULL) return -1; /***************************************************************************** * * * Insert the parcel into the priority queue. * * * *****************************************************************************/ memcpy(data, parcel, sizeof(Parcel)); if (pqueue_insert(parcels, data) != 0) return -1; return 0; }