• Choose a category
• All
• Classic-Fiction

By Root 1491 0

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.

Example 10.4. Implementation of Functions for Sorting Parcels

/*****************************************************************************

* *

* ------------------------------- parcels.c ------------------------------ *

* *

*****************************************************************************/

#include

#include

#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. *

* *

*****************************************************************************/