Implementing swimand sink for heap-ordered trees with explicit links while maintainingthe integrity of the handles is a challenge that we leave for exercises, becausewe shall be considering two alternative approaches in detail in Sections 9.6 and9.7.Ī full ADT such as Program 9.8 has many virtues, but it is sometimesadvantageous to consider other arrangements, with different restrictions on theclient programs and on implementations. class PQfull // ADT interface Īs we discussed in Section 9.1, the implementation given in Programs 9.9 and9.10 is suitable for applications where the priority queue is small and remove the maximum or find the maximum operations are infrequent otherwise, heap-based implementations are preferable. This interface for a priority-queue ADT allows client programs to deleteitems and to change priorities (using object handles provided by theimplementation) and to merge priority queues together. ![]() ![]() In this arrangement, clientprograms are responsible for keeping track of handles, which they may later useto specify which objects are to be affected by remove and changepriority operations, and which priority queues are to be affected by all ofthe operations. The insert operation returns a handle for each object addedto the priority queue by the client program. All operations refer to a particularpriority queue through a handle (a pointer to an object whose class is notspecified). It supports a situation wherea client has keys and associated information and, while primarily interested inthe operation of accessing the information associated with the highest key, mayhave numerous other data-processing operations to perform on the objects, as wediscussed at the beginning of this chapter. Program 9.8 gives a general interface for priority queuesalong the lines that we discussed in Section 4.9. When we want to remove an item from a priority queue, how do wespecify which item? When we want to maintain multiple priority queues, how do weorganize the implementations so that we can manipulate priority queues in thesame way that we manipulate other types of data? Questions such as these are thetopic of Chapter 4. We examine an implementation ofthis idea in detail here, both because we shall be using priority queues in thisway later in the book and because this situation is prototypical of the problemswe face when we design interfaces and implementations for ADTs. This arrangement is akin to use of the indirect-sort or the pointer-sort concepts described in Chapter 6.In particular, this approach is required for operations such as changepriority or remove to make sense. That is, we assignpriorities and use priority queues for only the purpose of accessing otherinformation in an appropriate order. Your simulator must output the name of the job running on the CPU in each time slice and must process a sequence of commands, one per time slice, each of which is of the form "add job name with length $n$ and priority $p "$ or "no new job this slice".Algorithms in Java, Parts 1-4, 3rd Editionįor most applications of priority queues, we want to arrange to have thepriority-queue method, instead of returning values for remove themaximum, tell us which of the records has the largest key, and towork in a similar fashion for the other operations. For simplicity, you may assume jobs cannot be interrupted-once it is scheduled on the CPU, a job runs for a number of time slices equal to its length. ![]() In this simulation, each job will also come with a length value, which is an integer between 1 and 100, inclusive, indicating the number of time slices that are needed to process this job. ![]() From among all jobs waiting to be processed in a time slice, the CPU must work on a job with highest priority. Each job is assigned a priority, which is an integer between -20 (highest priority) and 19 (lowest priority), inclusive. Your program should run in a loop, each iteration of which corresponds to a time slice for the CPU. In this project you are to build a program that sched. One of the main applications of priority queues is in operating systems- for scheduling jobs on a CPU.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |