You are to code a Heap, specifically a MinHeap, that is backed by an array of contiguous elements. Here is a tree and array representation of the same MinHeap: see image.
A MinHeap is a type of binary tree with two main properties.
These properties guarantee that the smallest element in the heap will be at the root of the heap.
Although heaps are usually classified as a type of tree, they are commonly implemented using an array due to their completeness. In your implementation, you should leave index 0 empty and begin your heap at index 1. This will make the arithmetic to find parents and children simpler.
To find the children of index i, 2i is the index of the left child (if one exists) and 2i + 1 is the in- dex of the right child (if one exists). Conversely, the parent of index i is index i/2 (integer division). Recall that Java automatically performs integer division when dividing two ints.
You should implement two constructors for this heap. One constructor initializes an empty heap with the capacity specified by a constant in MinHeap.java. The other constructor should implement the BuildHeap algorithm that was taught in lecture, which is an algorithm that creates a heap in O(n) time. Simply adding the elements one by one will not receive credit since it would be O(n log(n)) in the worst case; see the javadocs for this constructor for more specifications.
You may assume that your implementation does not need to handle duplicate elements. That is, the add method will never be passed duplicates and the remove method will never have to deal with the heap having duplicates. To be clear, your implementation would most likely work even if we were to test for duplicates; however, this will help remove ambiguity surrounding grading and testing your implementation.
Unlike BST, you are not required to use recursion in this assignment. Use whatever you find most intuitive - recursion, iteration, or both. However, regardless of the technique you use, make sure to meet efficiency requirements.
MinHeap.java
import java.util.ArrayList;
/**
* Your implementation of a MinHeap.
*/
public class MinHeap< T extends Comparable< ? super T > > {
/**
* The initial capacity of the MinHeap when created with the default
* constructor.
*
* DO NOT MODIFY THIS VARIABLE!
*/
public static final int INITIAL_CAPACITY = 13;
// Do not add new instance variables or modify existing ones.
private T[] backingArray;
private int size;
/**
* Constructs a new MinHeap.
*
* The backing array should have an initial capacity of INITIAL_CAPACITY.
* To initialize the backing array, create a Comparable array and then cast
* it to a T array.
*/
public MinHeap() {
}
/**
* Creates a properly ordered heap from a set of initial values.
*
* You must use the BuildHeap algorithm that was taught in lecture! Simply
* adding the data one by one using the add method will not get any credit.
* As a reminder, this is the algorithm that involves building the heap
* from the bottom up by repeated use of downHeap operations.
*
* Before doing the algorithm, first copy over the data from the
* ArrayList to the backingArray (leaving index 0 of the backingArray
* empty). The data in the backingArray should be in the same order as it
* appears in the passed in ArrayList before you start the BuildHeap
* algorithm.
*
* The backingArray should have capacity 2n + 1 where n is the
* size of the passed in ArrayList (not INITIAL_CAPACITY). Index 0 should
* remain empty, indices 1 to n should contain the data in proper order, and
* the rest of the indices should be empty.
*
* @param data a list of data to initialize the heap with
* @throws java.lang.IllegalArgumentException if data or any element in data
* is null
*/
public MinHeap(ArrayList< T > data) {
}
/**
* Adds an item to the heap. If the backing array is full (except for
* index 0) and you're trying to add a new item, then double its capacity.
* The order property of the heap must be maintained after adding. You can
* assume that no duplicate data will be passed in.
*
* @param data the data to add
* @throws java.lang.IllegalArgumentException if data is null
*/
public void add(T data) {
}
/**
* Removes and returns the min item of the heap. As usual for array-backed
* structures, be sure to null out spots as you remove. Do not decrease the
* capacity of the backing array.
* The order property of the heap must be maintained after removing.
*
* @return the data that was removed
* @throws java.util.NoSuchElementException if the heap is empty
*/
public T remove() {
}
/**
* Returns the minimum element in the heap.
*
* @return the minimum element
* @throws java.util.NoSuchElementException if the heap is empty
*/
public T getMin() {
}
/**
* Returns whether or not the heap is empty.
*
* @return true if empty, false otherwise
*/
public boolean isEmpty() {
}
/**
* Clears the heap.
*
* Resets the backing array to a new array of the initial capacity and
* resets the size.
*/
public void clear() {
}
/**
* Returns the backing array of the heap.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the backing array of the list
*/
public T[] getBackingArray() {
// DO NOT MODIFY THIS METHOD!
return backingArray;
}
/**
* Returns the size of the heap.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the size of the list
*/
public int size() {
// DO NOT MODIFY THIS METHOD!
return size;
}
}
MinHeapStudentTest.java
import org.junit.Before;
import org.junit.Test;
import java.util.ArrayList;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertSame;
import static org.junit.Assert.assertTrue;
/**
* This is a basic set of unit tests for MinHeap.
*
* Passing these tests doesn't guarantee any grade on these assignments. These
* student JUnits that we provide should be thought of as a sanity check to
* help you get started on the homework and writing JUnits in general.
*
* We highly encourage you to write your own set of JUnits for each homework
* to cover edge cases you can think of for each data structure. Your code must
* work correctly and efficiently in all cases, which is why it's important
* to write comprehensive tests to cover as many cases as possible.
*/
public class MinHeapStudentTest {
private static final int TIMEOUT = 200;
private MinHeap< Integer > minHeap;
@Before
public void setUp() {
minHeap = new MinHeap< >();
}
@Test(timeout = TIMEOUT)
public void testInitialization() {
assertEquals(0, minHeap.size());
assertArrayEquals(new Comparable[MinHeap.INITIAL_CAPACITY],
minHeap.getBackingArray());
}
@Test(timeout = TIMEOUT)
public void testBuildHeap() {
/*
6
/
8 4
/
2 1
- >
1
/
2 4
/
6 8
*/
ArrayList< Integer > data = new ArrayList< >();
data.add(6);
data.add(8);
data.add(4);
data.add(2);
data.add(1);
minHeap = new MinHeap< >(data);
assertEquals(5, minHeap.size());
Integer[] expected = new Integer[11];
expected[1] = 1;
expected[2] = 2;
expected[3] = 4;
expected[4] = 6;
expected[5] = 8;
assertArrayEquals(expected, minHeap.getBackingArray());
}
@Test(timeout = TIMEOUT)
public void testAdd() {
/*
1
/
2 6
/
4 8
*/
minHeap.add(4);
minHeap.add(2);
minHeap.add(6);
minHeap.add(1);
minHeap.add(8);
assertEquals(5, minHeap.size());
Integer[] expected = new Integer[MinHeap.INITIAL_CAPACITY];
expected[1] = 1;
expected[2] = 2;
expected[3] = 6;
expected[4] = 4;
expected[5] = 8;
assertArrayEquals(expected, minHeap.getBackingArray());
}
@Test(timeout = TIMEOUT)
public void testRemove() {
/*
1
/
2 4
/
8 6
- >
6
/
8
*/
minHeap.add(4);
minHeap.add(8);
minHeap.add(2);
minHeap.add(6);
minHeap.add(1);
assertEquals((Integer) 1, minHeap.remove());
assertEquals((Integer) 2, minHeap.remove());
assertEquals((Integer) 4, minHeap.remove());
assertEquals(2, minHeap.size());
Integer[] expected = new Integer[MinHeap.INITIAL_CAPACITY];
expected[1] = 6;
expected[2] = 8;
assertArrayEquals(expected, minHeap.getBackingArray());
}
@Test(timeout = TIMEOUT)
public void testGetMin() {
Integer temp = 1;
/*
1
/
2 3
/
4 5
*/
minHeap.add(temp);
for (int i = 2; i < 6; i++) {
minHeap.add(i);
}
assertSame(temp, minHeap.getMin());
}
@Test(timeout = TIMEOUT)
public void testIsEmptyAndClear() {
// Should be empty at initialization
assertTrue(minHeap.isEmpty());
// Should not be empty after adding elements
/*
1
/
2 3
/
4 5
*/
for (int i = 1; i < 6; i++) {
minHeap.add(i);
}
assertFalse(minHeap.isEmpty());
// Clearing the list should empty the array and reset size
minHeap.clear();
assertTrue(minHeap.isEmpty());
assertEquals(0, minHeap.size());
assertArrayEquals(new Comparable[MinHeap.INITIAL_CAPACITY],
minHeap.getBackingArray());
}
}