Description
This assignment focuses on implementing a Priority Queue ADT using different variations of heaps. Turn in all parts of this assignment electronically. Your turnin should consist of four files: MinMaxBinaryHeapPQ.java, FourHeapPQ.java, HW5PriorityQueueTest.java (you will modify the provided file to add some testing code), and README.txt. You will need the supporting files found off the course’s homework webpage: GenericPriorityQueue.java, BinaryHeapPQ.java, and HW5PriorityQueueTest.java. Step 0 is a paper warm-up exercise where you will practice inserting into and removing from heaps. In Step 1, you will write a generic, binary heap that is able to toggle between a min-heap and a max-heap depending on how it is constructed. In Steps 2 and 3, you will create a generic, four min-heap implementation in which each node in the heap can have up to four children. Step 0: Warm-up For each of the problems below, draw the heap that results after the requested operations are performed. You will not turn in your drawings. Instead, use the final heap drawing to list the values found in the heap in order from top to bottom, left to right. For example, if your answer produced a final binary heap with a root of 3, 11 as the root’s left child, 7 as the root’s right child, and 15 as 11’s left child, your answer would be “3, 11, 7, 15”. In other words, the order you list the values should be the same as the order they would be kept in an array implementation of a heap as described in lecture. Save the six lists of values (one for each problem) representing your final heap drawings in your README.txt. 1. Draw the heap that results when inserting the following values, one at a time, into an initially empty minimum binary heap: 10, 12, 1, 14, 6, 5, 8, 15, 3, and 9. 2. Draw the heap that results when inserting the following values, one at a time, into an initially empty maximum binary heap: 10, 12, 1, 14, 6, 5, 8, 15, 3, and 9. 3. Draw the heap that results when inserting the following values, one at a time, into an initially empty minimum four heap: 10, 12, 1, 14, 6, 5, 8, 15, 3, and 9. Draw your result as a four tree (a tree where each node can have up to four children) that maintains both the heap structure and min-heap ordering properties. 4. Draw the heap that results after performing three remove operations (i.e. three deleteMin operations) on the heap from #1. 5. Draw the heap that results after performing three remove operations (i.e. three deleteMax operations) on the heap from #2. 6. Draw the heap that results after performing three remove operations (i.e. three deleteMin operations) on the heap from #3. 2 of 4 Step 1: MinMaxBinaryHeapPQ The goal of this part of the assignment is to make a new class MinMaxBinaryHeapPQ that extends the generic BinaryHeapPQ to allow the client to decide if they would like to have a min-heap or a max-heap. Recall that a min-heap is one where every node in the heap is less than or equal to all of its children and a max-heap is a heap where every node is greater or equal to all of its children. The BinaryHeapPQ class already has the following constructors and methods (along with a few others): public BinaryHeapPQ() constructs an empty min-heap public void add(T value) adds a value to the min-heap public boolean isEmpty() returns true if the heap has no elements public T peek() returns (but does not remove) the minimum element in the heap public T remove() removes and returns the minimum element in the heap public int size() returns the number of elements in the heap public String toString() returns a String representation of BinaryHeapPQ with values stored with heap structure and order properties protected void bubbleDown() performs the “bubble down” operation to place the element that is at the root of the heap in its correct place so that the heap maintains the min-heap order property protected void bubbleUp() performs the “bubble up” operation to place a newly inserted element (i.e. the element that is at the size index) in its correct place so that the heap maintains the min-heap order property Your MinMaxBinaryHeapPQ should extend the BinaryHeapPQ class. Therefore, your MinMaxBinaryHeapPQ should have the following class header: public class MinMaxBinaryHeapPQ> extends BinaryHeapPQ At minimum, your MinMaxBinaryHeapPQ should have the following constructors and methods: • public MinMaxBinaryHeapPQ() This is your default constructor for MinMaxBinaryHeapPQ. It should be a min-heap by default. • public MinMaxBinaryHeapPQ(boolean isMinHeap) For this additional constructor, you should create MinMaxBinaryHeapPQ as a min-heap if isMinHeap is true or as a max-heap if isMinHeap is false. • protected void bubbleDown() This method overrides the BinaryHeapPQ’s bubbleDown method. In this overridden version, if your MinMaxBinaryHeapPQ was constructed as a min-heap, your method should perform the same as BinaryHeapPQ’s bubbleDown. However, if MinMaxBinaryHeapPQ was constructed as a max-heap, your method should perform the bubble down operation by bubbling the root element down to the correct place in the heap such that the heap maintains the max-heap order property after a remove has been performed. • protected void bubbleUp() This method overrides the BinaryHeapPQ’s bubbleUp method. If your MinMaxBinaryHeapPQ was constructed as a min-heap, your method should perform the same functionality as BinaryHeapPQ’s bubbleUp. However, if MinMaxBinaryHeapPQ was constructed as a max-heap, your method should perform the bubble up operation by bubbling the last inserted value up to the correct place in the heap such that the heap maintains the max-heap order property. 3 of 4 Step 2: FourHeapPQ The goal of this part of the assignment is to write a generic, four min-heap. A four min-heap is similar to a binary min-heap but each node can have up to four child nodes. Your FourHeapPQ should implement the generic GenericPriorityQueue interface and maintain both the heap structure and the minimum heap order property. You should implement your FourHeapPQ using an array like we did for our BinaryHeapPQ. However, the computations to find the index of a node’s children and parent will be different. You will have to figure these out. Unlike a binary heap though, the math is a bit simpler if you put your first element at the 0th index instead of the 1st index as we did in the BinaryHeapPQ. If you decide to go this route, the way the size is maintained for the FourHeapPQ will be a different than the BinaryHeapPQ. If you decide to put the 1st element in the 0th index and you don’t adjust the FourHeapPQ’s size properly, you will likely get NullPointerExceptions. The toString method of your FourHeapPQ should use Arrays.toString to print out the elements in your array (see BinaryHeapPQ’s toString method for reference). We are providing you a few methods that you can use to help you test your FourHeapPQ. The testing code provided is found in HW5PriorityQueueTest.java. However, you should add your own test cases to this file and turn it in along with your FourHeapPQ.java. You will be graded on how well you have tested your code. Step 3: Write-Up In addition to the code that you turn in, answer the following questions in a file called README.txt. 1. On inserts, do you expect BinaryHeapPQ or FourHeapPQ to perform better? Explain why. 2. On remove, do you expect BinaryHeapPQ or FourHeapPQ to perform better? Explain why. 3. Using the buildBinaryHeap and buildFourHeapPQ methods in the given HW5PriorityQueueTest.java file, perform inserts of different sizes and time them. Choose a number of different sizes and include them and the timing results in your README.txt. Empirically, which heap is performing better for inserts? Is it what you expected? If not, why do you think this may be the case? 4. Using the emptyHeap method in the given HW5PriorityQueueTest.java file, perform different number of removes on BinaryHeapPQ and FourHeapPQ and time them. Choose a number of different sizes and include them and the timing results in your README.txt. Empirically, which heap is performing better for removes? Is it what you expected? If not, why do you think this may be the case? 4 of 4 Style Guidelines and Grading Part of your grade will come from appropriately utilizing an array data structure to implement your MinMaxBinaryHeapPQ.java and FourHeapPQ.java classes. There will be significant deductions if you use Java collections to implement these classes. Additionally, you should not use any other auxiliary data structures other than the single array in your implementations. Redundancy is another major grading focus; some methods are similar in behavior or based off of each other’s behavior. You should avoid repeated logic as much as possible. Your class may have other methods besides those specified, but any other methods you add should be private. You should follow good general style guidelines such as: making fields private and avoiding unnecessary fields; appropriately using control structures like loops and if/else; properly using indentation, good variable names and types; and not having any lines of code longer than 100 characters. Comment your code descriptively in your own words at the top of your class, each method, and on complex sections of your code. Comments should explain each method’s behavior, parameters, return, and exceptions. The files provided to you use the “doc comments” format used by Javadoc, but you do not have to do this. For reference, our solution for MinMaxBinaryHeapPQ.java is 55 lines long (29 lines if you ignore blank, closing braces, and commented lines) and our solution for FourHeapPQ.java is approximately 184 lines long (79 lines if you ignore blank, closing braces, and commented lines).
