This lab will investigate the implementation of leftist heaps, and compare their performance to binary heaps.

1. Copy the files:
   • main.cpp
   • leftist_tree.h
   Create a new project as usual and look over the files. The main program is a simple application that creates a priority queue and measures the time to add and then remove a number of integers.

   You are also given the public interface to a class implementing a priority queue as a leftist heap. Read through the file comments and make sure you understand what each method is supposed to do. You will be providing the implementation for the class, and modifying the main program to use your new class.

2. Test the binary heap. Compile and run the main program. You should adjust the number of values that are inserted so that the time reported is about 1 second.

3. Modify the main program. Change the declaration of the variable pq to be a leftist heap. Also add a statement to include the file leftist_heap.h into the main program.

   Now you will implement the leftist heap.

4. The node class. A leftist tree is a linked data structure and relies on "nodes" to store the data. Each node will contain the data and pointers to the left and right children, as in a normal binary tree. (No parent pointer is necessary.) In addition, each node will also store its "null path length", the length of the shortest path to a descendent node with at most one child.

   Create the node class (you may find it simpler to make it an external class rather than nesting it in the leftist tree class). Remember that it should be a template class.

5. Private instance variables. The leftist tree itself will need a private instance variable that points at its root node. Add this now.

   You will also need to write several private member functions, described below.

6. Recursively deleting nodes. The first private function should take a pointer to a node and should delete that node and all of its descendants. This is best done recursively. Don't forget the base case.

7. Recursively copying nodes. Similar to the above, this function should take a pointer to a node and should copy that node and all of its descendants. It should return a pointer to the copy. Again, this is most easily done as a recursive function.

8. Merging two trees. You need two more private functions, which together will recursively merge two leftist trees. Each will take two pointers to nodes, and will return a pointer to the root of the new merged tree.

   The first function will do all the work, but will make some assumptions about its arguments:

   • Neither argument is a null pointer.
   • The first node has a smaller data value than the second.

   Recall that the algorithm for this recursive merge is as follows:

   if the first node has no left child
      then make the second node the left child of the first
   otherwise:
      merge the second node with the right child of the first
      (do not recursively call this function directly; instead
       you will call the function below)
      the merged leftist tree becomes the right child of the first node,
         which is now the root of the merged tree
      ensure the leftist tree invariant is satisfied by swapping
         the children of the root node if the left child has a shorter
         null path length than the right
      update the null path length of the root node;
         it will be one more than the null path length of its right child
   

   The second function simply ensures that the assumptions required by the first are satisfied and then calls it. To do this:

   • If either node is a null pointer, no merge is necessary; simply return the other node.
   • Otherwise, check which node contains the smaller data value and pass it as the first argument to the function above.

   ---

   If you have made it this far, you are almost done. All that remains is to implement the public member functions, which will be easy given the private functions above.

9. Constructor. The default constructor needs to initialize the root of the tree. The tree should be empty.

10. Destructor. The destructor needs to delete all the nodes in the tree. Use the private function above for this.

11. Copy constructor. The copy constructor should initialize the root of the tree to be a copy of its argument. Again, use the private function you wrote above for this.

12. Assignment operator. Assignment is almost the same as the copy constructor. You need to do two additional things: First, check that you are not assigning a tree to itself (hint: compare "this" and the argument). Second, before creating the copy, you need to get rid of any existing nodes in the tree.

13. Adding new values. The "push" function should create and initialize a new node, merge it with the existing root, and set the root to the result. Think about what the null path length of this new node will be. (Hint: does it have any children initially?)

14. Removing a value. To remove the highest priority value, the "pop" function should delete the old root node, merge the two children of the root, and set the root to the result.

15. Getting the highest priority value. The "top" function should return a reference to the data stored in the root node.

16. Is it empty? The "empty" function should check if there are any nodes in the tree.

17. Merging with another leftist heap. The "merge" function is similar to assignment, but it merges the two trees. Like assignment, you should check that you don't try to merge a tree with itself. Following the merge, the tree passed as an argument should be empty.

18. Running the program. You should now be able to recompile and run the main program. How does the performance of the leftist heap compare with that of the binary heap used in the STL priority queue? Can you think of a reason for any difference?

19. Improvements. If you still have time left, you might try modifying your leftist tree class to allow a function object to be used as the comparison function rather than just the less than operator.

At the conclusion of this lab, take a moment to review the following:

You have explored the implementation of leftist heaps, and compared their performance to binary heaps.