## 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

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).