Priority Queues

CS 206 - Introduction to Data Structures

Assignment 8: Due 12:01 AM Thursday Nov 14

(Yes, 1 minute after midnight to avoid bad numbers.
Election day has just passed which means it is less than 1 year until the next presidential election. To celebrate this observation in this assignment we will deal with polling data for candidates in the Democratic party. (All of the data is fairly old.)

We will use this data within a Heap / priority queue.

The data files for this assignment are in /home/gtowell/Public206/a8/dem* You may copy these files as you need for development. However, your program must be able to read these files from this location (or a different location of my choosing) during testing.

Requirements:

Implement an array-based binary tree that implements BinaryTreeInterface.java. /home/gtowell/Public206/a8/BinaryTreeInterface.java

You are not required to use only recursive implementation techniques
Remember that a binary tree is not guaranteed to be complete (for example, the user might execute remove on any element any time). You need to handle the case where positions may be, or become, null through out your tree.
Override toString to return an inorder traversal of the nodes of the tree. That is, if the nodes contain the integers 6, 4, 2, 7, 3, 9, 8, 5, then an inorder traversal would print 2, 3, 4, 5, 6, 7, 8, 9.
Add a method toStringBreathFirst which returns a string containing the elements of the tree traversed in breath-first traversal order. A breadth first traversal prints out all nodes at level N together and prior to an nodes at level N+1. For example, for the integers 6, 4, 2, 7, 3, 9, 8, 5 a breadth first printout might be
```
   L1(6) L2(4,7) L3(2, 5, x, 9) L4(x, 3, x, x, x, x, 8, x) 
```
where x indicates null. Note that a breadth first traversal of an array-based tree is considerably easier than for a link-based tree.

Now implement the PriorityQueue interface (from /home/gtowell/Public206/a8/PriorityQueueInterface.java) as an array-based Heap which extends your array-based Binary Tree. Note that it is recommended to add protected or private helper methods in both the tree and heap as you design deems necessary. Your implementation should be properly encapsulated, i.e. no implementation details should be made visible outside of the heap or tree classes.
- Your implementation of insert should use the compareTo method of the given element to determine which order to arrange the priority queue. Insertion of elements that are already in the tree should update the current element in the priority queue while making any updates necessary to guarantee the heap property. When you put your polling data into the tree this will be equivalent to updating the poll numbers for a candidate. Since this heap will be used to store polling data, you should implement this as a maximum heap, so that it will be easy to retrieve the current top candidate.
- Your implementation of remove should ensure the heap property is maintained. If the given element can not be found in the heap (based on the use of the compareTo method), this method should do nothing and return false.

Getting the top candidates

While a heap is usually required only to return the maximum (or minimum) element, since this will be used to store polling data, it may be interesting to us to retrieve the top few candidates.

Requirements:

Add a method ArrayList<E> peekTopN(int n) that returns the top elements of the heap in order. The heap should not be any different after the method was called than it was before the method was called, i.e., this is similar to peek in that it does not remove the top element. You should not implement this method by removing and then reinserting each element, as this has the potential to modify the heap.
Describe your design of the peekTopN method in your README file and give a big-O analysis.

Command Line Inputs

Your program must be able to take filenames that store polling data as arguments to your main method. Your resulting heap should contain the polling data for each candidate from the most recent date for which there is data from the files given on the command line. The resulting heap should be ordered so that the candidate with the highest percentage of voters in the most recent poll is at the top of the heap. Additionally, you will add an option for the users to provide a flag that will run your peekTopN method to determine and print out the top N candidates. The resulting arguments you should handle will look like this:

 -n 5 dempres_20190210_1.csv dempres_20190210_2.csv

In the above case, the top 5 candidates would be displayed.

Requirements:

Take filename input from the command line into the main method of your Main.java. You may be given multiple filenames. Process an optional flag to print out the top N candidates. These should be printed out like this (where the example given is for N = 2):
```
     Top 2 Candidates:
     Joseph R. Biden Jr.:29.0
     Kamala D. Harris:15.0
```
The above printout should happen once after all polling data has been read and inserted into your data structure.
In the absence of the "-n" flag, you should program should assume that n is 1.
You many assume that the list of filenames is always last, i.e. the first non-flag argument you encounter is assumed to be the beginning of the list of file names. Make sure you error-check thoroughly, both the arguments to the flags and the flags themselves. Your program should behave rationally no matter how unreasonable the input or the value of flags. (This should be fairly easy as there is only one flag.)
After each polling file is inserted you should print out the heap (in order).

Extra Credit

All extra credit should only be done after successful completion of all of the base requirements for this assignment. No extra credit will be given on incomplete assignments. The number of points awarded for extra credit will be smaller than those for completion of the base requirements and the extra credit is designed to be harder than those basic requirements as well. You may choose which of the extra credit options below to pursue and can receive credit for some and not others where that makes sense. In the case that you implement ANY extra credit, you must list them in your README so that I will know to test for them and grant credit accordingly.

Handle tied ranks appropriately for the peekTopN method. For example, in the case where there are two candidates who are tied for the best, peekTopN for n = 1 should print out both of those candidates.
Obtain more recent polling data and format it so that matches the format of the existing data. For each polling data instance, in your readme file you must indicate where you obtained the data and from what source that data was obtained. A complete URL is necessary, but is not sufficient. You will receive credit for up to 5 polling data instances. However, credit is on a sliding scale so the fifth is worth far less than the first. Also, in case multiple people submit the same polling data, I reserve the right to divide points equally among the submitters. That is, if 1 person submits a polling data instance, it might be worth M points. If N people submit the same poll, then each person would receive M/N points.