MCX2                                                                                                                 Math Department
Mr. Gary Jaye                                                                                                    Danny Jaye, A.P.S.

1995 APCS AB Exam: Question 2

This question involves reasoning about two implementations of of a data structure called a priority list. 
A priority list  is a collection of items, each of which contains both data and a unique integer priority. The 
''maximal'' item in a priority list is the element whose integer priority has the greatest value. Both data and 
an integer priority are specified when inserting an element into a priority list. Only the maximal element, 
the item with the highest integer priority, is accessible in a priority list. 

A priority list class Plist supports the following public member functions.   

Consider the following two methods for implementing priority lists. Type declarations are given in part (b) of 
this problem. 

Method 1: A priority list is an unsorted linked list. The Insert operation inserts an item as the first node 
of the list. 

Method 2: A priority list is a linked list sorted by priority field from largest to smallest (so that the first node 
in the list is always the maximal item of the priority list). The Insert operation inserts an item so that the list remains 
sorted by priority. 

Precise specifications for the member functions described above are given below. 

Plist::Plist()
//postcondition: represents an empty priority list

bool Plist::IsEmpty() const
//postcondition: returns true if priority list is empty (has 0 items);
//               otherwise, returns false

void Plist::Insert(const DataType & info, int pri)
// precondition: no item in priority list has priority pri
// postcondition: A new item whose data field has value info and whose
//                priority field has value pri has been inserted

void Plist::FindMax(DataType & info, int & pri) const
// precondition: IsEmpty() == false, (priority list is non-empty)
// postcondition: the values of info and pri are those of the maximal item

void Plist::DeleteMax()
// precondition: IsEmpty() == false, (priority list is non-empty)
// postcondition: the maximal item has been deleted

part A 
Complete the table below, In each cell give the worst-case time complexity for the corresponding operation and implementation
of a priority list of n items. Use O-notation and briefly justify each answer. 

part B 
In this part, you will write functions Insert and FindMax for one of the methods for implementing priority lists 
described at the beginning of this question. You MUST use the same method in writing both Insert and FindMax. 
It may be the case that it is easier to write code for one of the methods than for the other. Think carefully before 
choosing a method. Circle below the method you will use to implement Insert and FindMax. 

Method 1   or   Method 2 

You must use the following type declarations to implement priority lists regardless of which method you chose. 

     class DataType;

     struct Node {
         DataType data;     // data associated with item
         int priority;      // unique priority associated with item
         Node * next;
     };

     class Plist { 
       public:
          Plist();
          int IsEmpty() const;
          void Insert(const DataType &, int);
          void FindMax(DataType &, int &) const;
          void DeleteMax();
       private:
          Node * myFirst;     // pointer to first node in linked list
     };

Complete functions Insert() and FindMax() below the following headers. 

void Plist::Insert(const DataType & info, int pri)
// precondition: no item in priority list has priority pri
// postcondition: A new item whose data field has value info and whose
//                priority field has value pri has been inserted

void Plist::FindMax(DataType & info, int & pri) const
// precondition: IsEmpty() == false, (priority list is non-empty)
// postcondition: the values of info and pri are those of the maximal item