• Practice constructing and using heap data structure as a priority queue ADT
• Practice writing merge operation in skew and leftist heap data structures
• Gain additional experience constructing and using binary trees
• Practice using recursion in programs
• Learn to use function pointers

In recent years more people are joining college programs to obtain expertise in some high demand fields. The departments that are experiencing the surge always look for more efficient ways for deploying their limited resources. A task is assigned to you to implement a proposed intelligent algorithm for the purpose of simulating and testing the algorithm. This intelligent algorithm automatically registers students in a course based on a priority value for every student. The students will be registered in the order of priority values. The priority for a student is defined based on some criteria. We can change the algorithm which determines the priority value. The algorithm to determine the priority will be implemented in a function. In such a system changing the function can change the priority for a student. The system uses a heap data structure to store the information in a priority queue. Your job is to implement a heap (skew/leftist) that can use different priority functions. Such an architecture allows us to use different priority functions and compare the results.

Skew Heap

A skew heap is a specialized version of a heap data structure which performs the insertion and deletion operations in O(log n) amortized time. This data structure is a binary tree in which the root always holds the node with the highest priority. Skew heap uses merge operation to perform insertion and deletion.

The major operations supported by a skew heap are insertion of elements, reading the highest priority element, and removing the highest priority element. Reading the highest priority element is just a matter of reading the root node of the heap. The other two operations, insertion and removal, are applications of the merge function:

• To insert a new node x into an existing skew heap H, we treat x as a single-node skew heap and merge it with H.
• To remove the node with highest priority value, we delete the root node and then merge the root's left and right sub-heaps.

The special feature of a skew heap is the merge operation which combines two skew heaps into a single, valid skew heap. Let p1 and p2 be positions in two skew heaps (e.g. pointers to nodes). The merge operation is defined recursively:

• If p1 is Null, return p2; similarly, if p2 is Null, return p1.
• Assume that p1 has higher priority than p2; if not, swap, p1 and p2.
• Swap the left and right subtrees of p1.
• Recursively merge p2 and the left subtree of p1, replacing the left subtree of p1 with the result of the recursive merge.

Leftist Heap

A leftist heap is similar to skew heap and it uses a merge operation for insertion and deletion. However, it maintains a specific property and it uses the property during the merge operations. Every node in a leftist heap stores a value called Null Path Length (NPL). This value presents the lowest number of edges from the node to a null node. In the other word the NPL value represents the shortest possible path from a node to a null node.

During a merge operation if the NPL value of the right child is larger than the NPL value of the left child we swap the children. This generally makes the left subtree heavier than the right subtree.

In this project, you will implement a priority queue class (RQueue) based on a skew-heap or a Leftist-heap data structure; it can maintain a min-heap or a max-heap based on the computed priority for every student, where the priority function is provided to the RQueue constructor via a function pointer. Inserting to and extracting from the skew/leftist heap uses a heap merge function which guarantees that the heap property (min-heap or max-heap) is maintained; the comparisons that are part of the merge process will be made on the computed priorities for the objects in the heap. The class allows for the priority function to be changed; in which case the heap must be rebuilt. Moreover, the data structure can switch between a skew heap or a leftist heap at the request of the class user. Such a request will trigger reconstruction of the heap.

For this project, you are provided with the following files:

• rqueue.h – The interface for Student, Node, and RQueue classes.
• rqueue.cpp – A skeleton for the implementation of the class RQueue
• driver.cpp – A sample driver program. It contains sample use of RQueue class.
• driver.txt – A sample output produced by driver.cpp

There are three classes in this project. The class RQueue has a member variable of type Node, and the class Node has a member variable of type Student.

Class Student

The implementation of this class is provided to you. You are not allowed to modify the class. This class stores the following information about a student:

• m_name stores a student's name. The name does not need to be unique.
• m_level stores the student's year in school. The possible values are defined in the enum type Level.
• m_major stores the major of the student. The possible values are defined in the enum type Major.
• m_group stores the group that the student belongs to. The possible values are defined in the enum type Group.
• m_race stores the declared race by the student. The possible values are defined in the enum type Race.
• m_gender stores the gender of the student which is self-declared. The possible values are defined in the enum type Gender.
• m_income stores the family income for the student. The possible values are defined in the enum type Income.
• m_highschool stores rank of the highschool that the student attended. The possible values are defined in the enum type Highschool.

Priority Functions

A priority function is a user defined function that can use the information in the class Student to determine a priority value for a student. Two example functions are provided in driver.cpp file. You can define your own priority functions. In fact, different schools may have different criteria for this purpose. The ability of using different functions allows us to adapt to different priority algorithms. The heap can accept a prioritization function. This is accomplished by passing a function pointer to the constructor. The function pointer is the address of a function that will be used to compute the priority for students. The function must take a Student object as input and return an integer priority value. A typedef for the function pointer is provided for you in rqueue.h:

  typedef int (*prifn_t)(const Student&);

Class Node

This class constructs a node in the heap data structure. It has a member variable of the type Student. The member variable is initialized through the Node constructor. The class RQueue is a friend of Node class, it means it has access to private members of Node class. You are not allowed to modify this class.

Overloaded Insertion Functions

There are two overloaded insertion functions for the classes Student and Node to help you debugging the project. The implementation is provided to you. You do not need to modify them.

Class RQueue

The class RQueue constructs a skew or a leftist data structure of the type min-heap or max-heap. This class has a member variable called m_heap. The member variable m_heap presents the root node of the heap data structure and it is of the type Node. The following table presents the list of member functions that need implementation.

• Private helper functions must be declared in rqueue.h. No other modifications to rqueue.h are permitted!
• No STL containers or additional libraries may be used in the implementation of the project classes. However, you can use STL containers in the Tester class for the testing purposes.
• The required functionality is provided in the Student and Node classes. There is no need for any modifications to the implementation of these classes.
• Your code should not have any memory leaks or memory errors.
• In the case of a leftist heap the lowest level of nodes which store the keys have zero NPL value.
• Computed priority values may not be pre-computed and stored with the Student object in the queue. They must be computed as needed using the priority function.
• Insertion to and extraction from the heap must run in amortized logarithmic time.
• Follow all coding standards as described on the C++ Coding Standards. In particular, indentations and meaningful comments are important.

• The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
• The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
• You are responsible for thoroughly testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
• You must write a separate function for every test case.
• Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
• Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
• An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
• The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing RQueue class

Note: The majority of tests need to check whether the heap property is satisfied after the operations. You might want to implement a helper function in your Tester class that performs such a functionality. Then, this helper can be called in multiple test functions.

• Test insertion for a normal case of min-heap. After a decent number of insertion (e.g. 300 nodes) we traverse the tree and check that the heap property is satisfied at every node.
• Test insertion for a normal case of max-heap. After a decent number of insertion (e.g. 300 nodes) we traverse the tree and check that the heap property is satisfied at every node.
• Test removal for a normal case of min-heap. After a decent number of insertion (e.g. 300 nodes) we check whether all removals happen in the correct order.
• Test removal for a normal case of max-heap. After a decent number of insertion (e.g. 300 nodes) we check whether all removals happen in the correct order.
• Test all nodes in a leftist heap have the correct NPL value.
• Test a leftist heap preserves the property of such a heap, i.e. at every node the NPL value of the left child is greater than or equal to the NPL value of the right child.
• Test whether after changing the priority function a correct heap is rebuilt with the same data (nodes) and the different priority function.
• Test merge of an empty queue (an edge case) with a normal queue. This is a call to the function RQueue::mergeWithQueue(RQueue& rhs) where rhs is a normally populated queue.
• Test the RQueue class copy constructor for a normal case.
• Test the RQueue class copy constructor for an edge case.
• Test the RQueue class assignment operator for a normal case.
• Test the RQueue class assignment operator for an edge case.
• Test that attempting to dequeue an empty queue throws an out_of_range exception.
• Test that attempting to merge queues with different priority functions throws a domain_error exception.

Random Numbers for Testing

For testing purposes, we need data. Data can be written as fixed values or can be generated randomly. Writing fixed data values might be a tedious work since we need a large amount of data points. The approach for creating data will be your decision.

In the file driver.cpp there is the class Random which generates pseudorandom numbers. The class is using a default seed value. On the same machine it always generates the same sequence of numbers. That is why the numbers are called pseudorandom numbers, they are not real random numbers. Please note, the numbers are machine dependent, therefore, the numbers you see in the sample file driver.txt might be different from the numbers your machine generates.

Memory leaks and errors

• Run your test program in valgrind; check that there are no memory leaks or errors.
  Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the lines numbers where the errors are detected and can usually tell you which line is causing the error.
• Never ignore warnings. They are a major source of errors in a program.

You must submit the following files to the proj3 directory.

• rqueue.h
• rqueue.cpp
• mytest.cpp (This file contains your Tester class, all test functions, all test cases, priority functions, and the main function.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command:

   cp rqueue.h rqueue.cpp mytest.cpp ~/cs341proj/proj3/

The following presents a course rubric. It shows how a submitted project might lose points.

• Conforming to coding standards make about 10% of the grade.
• Your test program is worth 50%. If you submit the sample driver program as your test program or no test program is submitted there will be 50% deduction.
• Correctness and completeness of your test cases (mytest.cpp) make about 15% of the grade.
• We have written test cases to test your submission without knowing anything about your code. Therefore, it is extremely important that your submission conforms to the specified requirements. Passing tests make about 30% of the grade.
• There is a 5% deduction for every modification that we need to perform to compile and run your work. For example, if we need to rename your file from myTest.cpp to mytest.cpp the deduction will be applied.

If the submitted project is in a state that receives the deduction for all above items, it will be graded for efforts. The grade will depend on the required efforts to complete such a work.