1.) I'm having difficulty testing me heap class. When I try to print my heap, it's giving me code instead of the array. I tried using toString() and DeeptoString() and neither worked.
2.) In my updateValue method. I realize that it doesn't know what to do once it's reached a node that has no children. It shoots me an index out of bounds. I think an easy way to check for that is to see if the left and right child index is greater or equal to the size. If it is...I guess I want it to do nothing.
Code below:
import java.util.NoSuchElementException;
public class MaxHeap {
public int[] heap;
private int size;
public static void main(String args[]){
MaxHeap testHeap = new MaxHeap(5);
testHeap.add(5);
testHeap.add(4);
testHeap.add(3);
testHeap.add(2);
testHeap.add(1);
System.out.println((testHeap));
testHeap.maxHeapify(0);
System.out.println(testHeap);
testHeap.extractMax();
System.out.println(testHeap);
testHeap.updateValue(1, 6);
System.out.println(testHeap);
}
/**
* _Part 0: Implement this constructor._
*
* Creates a new Heap instance initially capable of storing the specified
* number of elements.
*
* @param initialsize the initial size of the heap array
*/
public MaxHeap(int initialsize) {
// TODO: implement this
heap = new int [initialsize];
}
/**
* Provides read-only access to the heap's size. Size here is the number
* of *valid* items in the heap
*
* @return the number of items in the heap
*/
public int size() {
return size;
}
/**
* _Part 1: Implement this method._
*
* Adds an item to the heap maintaining the heap condition.
*
* An item is added to the next available slot in the array, and then
* bubbled up to its parent until the heap condition is restored.
*
* @param item
* the new int to add to the heap
*/
public void add(int item) {
// TODO: implement this
int parentIndex = (size-1)/2;
int childIndex = size;
heap[size] = item; //put it at the end
while (heap[parentIndex] < heap[childIndex] && parentIndex >= 0){ //check to make sure it's a proper heap
int temp = heap[parentIndex]; //start percolating up
heap[parentIndex] = heap[childIndex];
heap[childIndex] = temp;
childIndex = parentIndex;
parentIndex = (parentIndex-1)/2;
}
size+=1;
}
/**
* _Part 2: Implement this method._
*
* Restore the heap condition to a tree rooted at the specified index when
* the left and right subtrees obey the heap condition, but the root may
* not. This is also known as "Bubble Down".
*
* That is, given the specified index, and the fact that the left and
* right subtrees are heaps (if they exist), ensure that the largest of
* these three nodes get's swapped with the root, and then recursively
* restore the heap condition for the subtree with the element that was
* moved from the root.
*
* In essence, this method bubbles a value down from the root until the
* heap condition is restored.
*
* @param index
* the root tree to restore
*/
public void maxHeapify(int index) {
// TODO: implement this
int left, right, large, tmp; // declare variables left child, right child, largest node, temp for swap
int i = index;
left = 2 * i + 1; // left child
right = 2 * i + 2; // right child
if(left <= heap.length-1 && heap[left] > heap[i]) // find smallest child
large = left; // save index of smaller child
else
large = i;
if(right <= heap.length-1 && heap[right] > heap[large])
large = right; // save index of smaller child
if(large != i) // swap and percolate, if necessary
{
tmp = heap[i]; // exchange values at two indices
heap[i] = heap[large];
heap[large] = tmp;
maxHeapify(large);}
}
/**
* _Part 3: Implement this method._
*
* Removes the maximum valued item from the heap and restores the heap
* condition. If the heap is empty, this method should throw
* a NoSuchElementException
*
* This function is performed by:
*
* 1. removing the root of the heap
* 2. placing element from the end of the heap at the root
* 3. calling maxHeapify to restore the heap condition
* 4. making sure the size is updated
*
* @return the highest valued item from the heap
* @throws NoSuchElementException if called on an empty heap
*/
public int extractMax() {
// TODO: implement this
if (size < 1){
//throw no such element
throw new NoSuchElementException();
}
int max = heap[0];
heap[0] = heap[size-1];
size = size-1;
maxHeapify(0);
return max;
}
/**
* _Part 4: Implement this method._
*
* Checks to make sure that the *max* heap condition is upheld on a
* given array of integers.
*
* HINT: Full credit will be given on this one if you implement this
* method as a *recursive* function. It will probably make sense to
* create a private method that takes another argument (e.g., the index
* of the heap's root) to indicate where the checking should begin.
*
* My private method has the following signature:
* private static boolean check(int [] arry, int rootindx, int sz)
*
*
* @param array
* the array of data to check
* @param size
* the number of elements 'in' the heap (starting at index 0)
* @return true if the *max* heap condition is upheld
*/
public static boolean checkHeapCondition(int[] array, int size) {
// TODO: implement this
if (array != null)
return helpCheck(array,0, size);
return false;
}
//Helper method
private static boolean helpCheck(int[] arr, int i, int size) {
//Base case
if (i == size-1)
return true;
//2nd base case
if (2*i+1 >= size){
return true;
}
// check if a parent's value is larger or equal to both of
// its left child and right child
else if (arr[i] >= arr[2*i + 1] && arr[i] >= arr[2*i + 2])
return (helpCheck(arr, 2*i + 1, size) && helpCheck(arr, 2*i + 2, size));
else
return false;
}
/**
* _Part 5: Implement this method._
*
* Changes the value of an element in the heap. And bubbles the value
*
* @param index
* the index of the item to be modified
* @param newValue
* the new value of the specified item
* @return the old value of that item
* @throws IndexOutOfBoundsException if the specified index is invalid
*/
public int updateValue(int index, int newValue) {
// TODO: implement this
int parent = (index-1)/2;
int leftChild = (2*index +1);
int rightChild = (2*index+2);
if (heap == null || index >= size ){
throw new IndexOutOfBoundsException();}
int oldValue = heap[index];
heap[index] = newValue;
while (heap[parent] < heap[index] && parent >= 0 ){
int temp = heap[parent];
heap[parent] = heap[index];
heap[index] = heap[temp];
index = parent;
parent = (parent-1)/2;
}
//We need to check to see if the children don't exist
if (heap[leftChild] > heap[index] || heap[rightChild] > heap[index]){
maxHeapify(index);
return oldValue;
}
else return oldValue;
}
}
