CSE 12 PA7: Heaps and Priority Queue

Due date: Thursday, May 22nd @ 11:59 PM PST

There is an FAQ post on Piazza. Please read that post first if you have any questions.

Learning goals:

• Implement a MinHeap
• Understand and analyze the working of Priority Queues
• Write JUnit tests to verify proper implementation

Part 1: Testing and Implementation of MinHeap and MyPriorityQueue [95 points]

In this part of the assignment, you will implement a MinHeap and write JUnit tests to ensure that your implementation functions correctly.

Read the entire write-up before you start coding.

Download the starter code by cloning this repository.

+--PA 7 
|	+-- MinHeapInterface.java
|	+-- PublicTester.java		
|	+-- MyMinHeap.java			**Create this file**
|	+-- MyPriorityQueue.java		**Create this file**
|	+-- MyAlgorithm.java		        **Create this file**

In this assignment, we provide a PublicTester.java file that contains all the public test cases (visible on Gradescope) that we will use to test your MinMyHeap and MyPriorityQueue. We will not be grading your custom testers. We still encourage you to write your own tests to verify that your implementation follows the write-up specifications.

Part 1a - Implementation of MyMinHeap

Your task: Implement a MinHeap. In the MyMinHeap.java file, add the following:

Instance variables:

Instance Variable	Description
protected ArrayList<E> data	The underlying data structure of MyMinHeap. You must use 0-based indexing to store the heap (the root of the tree at index 0).

In this file, you may import the following:

• java.util.ArrayList
• java.util.Collection

MyMinHeap should have a constraint on the generic parameter E such that E implements Comparable<E> so you can compare the elements. You should also implement MinHeapInterface<E>.

Note: Do not add any other instance variables and do not add any static variables (other than private static final variables to be used as constants).

Constructors:

Constructor	Description
public MyMinHeap()	No-argument constructor that initializes data to an empty ArrayList.
public MyMinHeap(Collection<? extends E> collection)	Initializes a min-heap using the elements in collection. First, initialize data using the ArrayList(Collection<? extends E> collection) constructor by directly passing in the collection argument. Next, iterate through data backward, percolating each element down. We will soon write the percolateDown() helper method, which can be used here. Throws NullPointerException if collection or any element in collection is null.

Helper Methods:

You should find these methods useful to implement the actual functionality of MyMinHeap and also to implement other helper methods.

Important Note: These helper methods are meant to be called inside the core methods and other helper methods. Therefore, you have some design choice in the helper methods for 1) whether you want to assume all arguments are in-bounds and 2) if you do not want to assume, then what out-of-bounds behavior you want. If you assume all arguments are in bounds, you must make sure that all arguments follow the assumptions before calling your helper method.

Note:

• In practice, these would be private methods, but for our assignment, they will be protected so that we can auto-grade your methods and provide feedback for them. To be clear, these methods are required.
• All tests assume that you use 0-based indexing to store the heap in the array.

Helper Method Name	Description
protected void swap(int from, int to)	Swap the elements at from and to indices in data. You may assume from and to will be within bounds.
protected static int getParentIdx(int index)	Calculate and return the parent index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index > 0.
protected static int getLeftChildIdx(int index)	Calculate and return the left child index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index >= 0.
protected static int getRightChildIdx(int index)	Calculate and return the right child index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index >= 0.
protected int getMinChildIdx(int index)	Return the index of the smaller child of the element at index. If the two children are equal, return the index of the left child. If the node at index is a leaf (has no children), return -1. Note that it's also possible for a single node in our heap to have only one child. In this case, return the index of the left child (we know that this is a heap so all nodes are as far left as possible) You may assume that index will be within bounds. getMinChildIndex depends on what is currently in data, but does not make any changes to data.
protected void percolateUp(int index)	Percolate the element at index up until no heap properties are violated by this element (the heap properties will not be violated once this element's parent is not greater than it). Do this by swapping the element with its parent as needed. Note the case where the element that you are percolating is equal to the parent. In this case, the heap property requiring that a node be no greater than its children is already satisfied, so you should not swap the element you are percolating with the parent. You may assume that index will be within bounds. percolateUp makes changes in data.
protected void percolateDown(int index)	Percolate the element at index down until no heap properties are violated by this element (the heap properties will not be violated once this element is not greater than its children). If swapping is needed, always swap places with the smaller child. If both children are equal and swapping is needed, swap with the left child. Note the case where the element that you are percolating is equal to the smaller child. In this case, the heap property requiring that a node be no greater than its children is already satisfied, so you should not swap the element you are percolating with the child. You may assume that index will be within bounds. percolateDown makes changes in data.
protected E deleteIndex(int index)	Remove the element at index from data and return it. If we are removing the last element then the heap properties are maintained. In other cases, we will replace the deleted element with the last element in the heap (the right-most node in the bottom-most level of the heap) to fix the completeness property. Then, either percolate this element down or percolate this element up as necessary until no heap properties are violated by this element (only one of these actions will be necessary to maintain the heap property, all fixes to the key order property should be by percolating the replacement element). The deleteIndex explanation can be found in the Appendix You can assume that index will be within bounds. deleteIndex makes changes in data. Note: Make sure to remove from the ArrayList using the index and not the element as this could accidentally delete the wrong element if there are duplicates in the list.

Core Methods:

Method Name	Description
public void insert(E element)	Add element to the end of the heap (so that it is the right-most element in the bottom-most level) and percolate only the inserted element up until no heap properties are violated (all fixes to the heap properties should be by this percolation). Throw a NullPointerException and do not add to the heap if element is null. The insertion explanation can be found in the Appendix
public E getMin()	Return the root (this will be the smallest) element of the heap. If the heap is empty, return null instead.
public E remove()	Remove and return the root (this will be the smallest) element in the heap. Use deleteIndex() helper method here. If the heap is empty, return null instead.
public int size()	Return the number of elements in this min-heap.
public void clear()	Clear out the entire heap (the heap should be empty after this call).

Part 1b - Implementation of MyPriorityQueue

In this part of the assignment, you will understand how a priority queue can be implemented using a min heap.

Use MyMinHeap to implement MyPriorityQueue

public class MyPriorityQueue<E extends Comparable<E>>

A priority queue is a queue where elements are sorted by their priority. Popping/dequeuing from the priority queue should always yield an element with the highest priority. In other words, elements with higher priority will be closer to the front of the priority queue.

Our MyPriorityQueue implementation will be using a MyMinHeap backend. Our underlying data structure is a min-heap, so smaller elements (as defined by compareTo()) have higher priorities. The root node of the min-heap is the one with the highest priority and is also the smallest element in the min-heap.

MyPriorityQueue Instance Variables

protected MyMinHeap<E> heap;

• We will be using a single instance variable for our MyPriorityQueue. This MyMinHeap will contain all information we need to keep track of our heap. You should only use the MyMinHeap public methods in your MyPriorityQueue implementation. Do not directly access heap.list in your implementation of MyPriorityQueue (treat it as if it were a private instance variable).
• Note: Do not add any other instance variables and do not add any static variables (other than private static final variables to be used as constants).

protected MyMinHeap<E> heap

• This heap holds and sorts all elements for our priority queue. Since we are using our MyMinHeap to store our elements, null is not allowed in this priority queue.

MyPriorityQueue Constructors

public MyPriorityQueue();
public MyPriorityQueue(Collection<? extends E> collection);

public MyPriorityQueue()

• This no-argument constructor initializes heap to be an empty MyMinHeap.

public MyPriorityQueue(Collection<? extends E> collection)

• You may import java.util.Collection
• Throw a NullPointerException if collection or any element in collection is null.
• Otherwise, this constructor initializes heap to contain the elements in collection. Remember that we have already written a handy-dandy constructor for MyMinHeap.

MyPriorityQueue Methods

public void push(E element);
public E peek();
public E pop();
public int getLength();
public void clear();

public void push(E element)

• Throw a NullPointerException and do not add to the priority queue if element is null.
• Otherwise, add element to this priority queue. heap should be fixed accordingly.

public E peek()

• Return the element with the highest priority. Remember that this should be whichever element our min-heap says is the smallest element.
• If the priority queue is empty, return null instead.

public E pop()

• Remove and return the element with the highest priority. Remember that this should be whichever element our min-heap says is the smallest element. heap should be fixed accordingly.
• If the priority queue is empty, return null (and do no removal) instead.

public int getLength()

• Return the number of elements in the priority queue.

public void clear()

• Clear out the entire priority queue (the priority queue should be empty after this call).
• heap should be an empty MyMinHeap, not null, after this function is completed.

Part 1c: Application of Priority Queues

In this part of the assignment, you will use your implementation of a priority queue to find the kth largest value in an array

Your task: Create a new class called MyAlgorithm in a new file called MyAlgorithm.java.

Implement the following method:

public static Integer getKthLargest (ArrayList<Integer> list, int k)

• You are given an arrayList of integers and an integer k. You must find the kth largest integer in the list. This is the kth element of the list if it were to be sorted in decreasing order (i.e. not the kth largest distinct element). You may NOT sort the arrayList first. As such, your implementation must use a priority queue that stores at most k integers at a time and runs in O(nlogk) time.
• Throw a NullPointerException if list is null.
• Throw an IllegalArgumentException if list is empty.
• Throw an IllegalArgumentException if k is less than or equal to 0 or greater than the number of integers in the arrayList.
• Again, you are required to use a MyPriorityQueue object that stores at most k integers at a time in your implementation. Your algorithm must run in O(nlogk) time for full-credit.

For example:

Given a list [0, 10, 1, 9, 2, 8, 3, 7, 4, 6, 5] and integer k 3:

• You must return 8 as 8 is the 3rd integer in the sorted arrayList [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Given a list [2, 1, 2, 3] and integer k 3:

• You must return 2 as 2 is the 3rd integer in the sorted arrayList [3, 2, 2, 1]

Part 2: Coding Style (5 points)

Coding style is an important part of ensuring readability and maintainability of your code. We will grade your code style in all submitted code files according to the style guidelines. Namely, there are a few things you must have in each file/class/method:

• File header
• Class header
• Method header(s)
• Inline comments
• Proper indentation
• Descriptive variable names
• No magic numbers (Exception: Magic numbers can be used for testing.)
• Reasonably short methods (if you have implemented each method according to the specification in this write-up, you’re fine). This is not enforced as strictly.
• Lines shorter than 80 characters
• Javadoc conventions (@param, @return tags, /** comments */, etc.)

A full style guide can be found here and a sample styled file can be found here. If you need any clarifications, feel free to ask on Piazza.

Submission Instructions

Turning in your code

Submit all of the following files to Gradescope by May 22nd, 2025 @ 11:59 PM PST

• MyMinHeap.java
• MyPriorityQueue.java
• MyAlgorithm.java

Important: Even if your code does not pass all the tests, you will still be able to submit your homework to receive partial points for the tests that you passed. Make sure your code compiles in order to receive partial credit.

Appendix

How to compile and run the testers:

Running the tester on UNIX based systems (including a mac):

• Compile: javac -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. PublicTester.java
• Execute: java -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. org.junit.runner.JUnitCore PublicTester

Running the tester on Windows systems:

• Compile: javac -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" PublicTester.java
• Execute: java -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" org.junit.runner.JUnitCore PublicTester

Diagram for deleteIndex

deleteIndex() Figure 0: Begin deletion at index 0, which currently contains the element A.

deleteIndex() Figure 1: A is removed and set aside to be returned. The last element in the heap, G, is moved to the old position to replace it. We then begin the process of percolating G down. There is a violation because the element G is greater than the element D. Since both children are equal, we swap with the left child.

deleteIndex() Figure 2: G has now swapped with D, but there is still a violation because G is greater than E, so we will swap those two.

deleteIndex() Figure 3: G has now swapped with E and there are no more heap violations, thus ending the percolation process.We have completed the deletion process and will return the original deleted element, A.

Diagram for Insert

insert() Figure 0: Begin insertion of element D.

insert() Figure 1: Add D to the end of the min-heap.

insert() Figure 2: There is a violation since D is less than its parent G, so we will swap those.

insert() Figure 3: D has now swapped with 'G' and there are no more heap violations, thus ending the percolation process. We have completed the insertion process.