I'm just looking for some feedback on my implementation of a maxheap mostly relating to style. I'm trying to create good habits as I learn to program.
Note: for the sort method I was given the precondition that the passed in array never has empty/null elements and that it must be sorted in place.
public class Heap12<E extends Comparable<? super E>> implements PQueue<E>{ private E[] heap; // Backend data storage array private int size; // # elements in the heap Private constructor that is used by the sort() method to heapify an array of objects type E. Size is initialized to 0 so that the objects in the array can be sorted in place by calling the add(E e) method.
@param E[] e - the array to be heapified
@SuppressWarnings("unchecked") private Heap12(E[] e){ this.heap = e; // Set heap array to passed in array this.size = 0; // Size HAS to be 0 initially } Public default no-arg constructor that initializes size to 0 and the backing array to a default capacity.
@SuppressWarnings("unchecked") public Heap12(){ this.size = 0; // Default values this.heap = (E[]) new Comparable[5]; } Public copy constructor that takes in another Heap12<E> object. It creates a new Heap12<E> object that is a deep copy of the passed in object. The underlying objects of the backing array are shared, but each Heap12 has its own instance variables.
@param Heap12<E> o - the Heap12<E> object to be copied
@SuppressWarnings("unchecked") public Heap12(Heap12<E> o){ this.heap = (E[]) new Comparable[o.heap.length]; this.size = o.size; // Copy size for(int i = 0; i < o.size(); i++){ // Copy each element this.heap[i] = o.heap[i]; // reference } } Adds an element to this Heap12 object. Does not accept null elements, will throw a NullPointerException. If the Heap12 is at maximum capacity, the capacity will be doubled before adding the element.
@param E e - the element to be added to the Heap12
public void add(E e){ if(e == null) // Check for null element add throw new NullPointerException(); if(this.size() == heap.length) expandHeap(); // Double heap capacity if full heap[this.size()] = e; // Add the element at the rightmost leaflet bubbleUp(this.size()); // Move it to its proper place size++; } Returns the largest element contained in the Heap12 object (the root). Does not modify the heap.
@return E - the largest object (the object at the root)
public E peek(){ return heap[0]; } Removes the largest element in this heap (the root). If the heap is empty, null is returned.
@return E - the largest element (the root)
public E remove(){ E toReturn; if(this.isEmpty()) // Empty heap case return null; toReturn = heap[0]; // Return greatest element(root) heap[0] = heap[this.size() - 1]; // Put bottom rightmost at root heap[this.size() - 1] = null; // Get rid of the copy size--; trickleDown(0); // Move the new root to its proper // place return toReturn; } Determines if this Heap12 is equal to the passed in object. Returns false if the passed in object is not a Heap12, the two Heap12's have different sizes (# of elements), or if the two Heap12 objects do not have the same underlying data, in the same order.
@param Object o - the object to compare this Heap12 with @return boolean whether the two objects are equal
public boolean equals(Object o){ if( !(o instanceof Heap12) ) // Type check return false; Heap12 oQ = (Heap12) o; if(this.size() != oQ.size()) // Diff # elements means diff heaps return false; for(int i = 0; i < this.size(); i++){ // Loop through all the elements if( !(this.heap[i].equals(oQ.heap[i])) ) // if one is different return false; // heaps are not equal } return true; // If we get here, heaps are equal } Returns a hash code for this Heap12 object. The code is the same for objects that contain the same elements in the same order.
@return int - the hash code of this Heap12<E>
public int hashCode(){ int toReturn = 1; /* Add each elements hashCode to the total and multiples by 31 each time */ for(int i = 0; i < this.size(); i++){ toReturn = 31 * toReturn + heap[i].hashCode(); } return toReturn; } Checks to see if this Heap12<E> is empty (has no elements)
@return boolean - true if the Heap12 is empty, false if not
public boolean isEmpty(){ return size == 0; } Returns the number of elements in this Heap12<E> object as an int. @return - the number of elements in this Heap12 object.
public int size(){ return this.size; } Private helper method for remove(). This method reorders the underlying heap array after an element is removed so that the heap retains the max heap property and completeness.
@param int parent - the parent node index
private void trickleDown(int parent){ int left = (2 * parent) + 1; // Compute Left/Right child indices int right = (2 * parent) + 2; if(left > size - 1 ) // Base case: end of the heap return; /* If right child is null or left child >= right child, compare left child to parent */ if(heap[right] == null || heap[left].compareTo(heap[right]) >= 0){ if(heap[left].compareTo(heap[parent]) > 0){ swap(parent, left); // If the left child is > parent swap trickleDown(left); // Left index is now the parent index } } // If the right child > parent else if(heap[right].compareTo(heap[parent]) > 0){ swap(parent, right); // Swap the parent and right child trickleDown(right); // Right index is now the parent index } } Private helper method for add(E e). This method reorders the underlying heap array after an element is added so that the heap retains the max heap property and completeness.
@param int child - the child node index
private void bubbleUp(int child){ int parent = (child - 1) / 2; // Compute the parent index if(child == 0) // If we're at the root, stop bubbling return; // Added simply for clarity (not needed) if( heap[child].compareTo(heap[parent]) > 0 ){ // If child > parent swap(parent, child); // Swap them bubbleUp(parent); // parent is now the old child } } Private helper method that swaps a parent node element and a child node element using a temp variable.
@param int parent - the index of the parent object
@param int child - the index of the child object
private void swap(int parent, int child){ E temp = heap[parent]; // Store the parent heap[parent] = heap[child]; // Replace parent element with child heap[child] = temp; // Replace child with the parent } Private helper method that doubles the capacity of the underlying array of this Heap12 object. Used when trying to add an element to a heap where size == capacity.
@SuppressWarnings("unchecked") private void expandHeap(){ // Create new array with double capacity E[] temp = (E[]) new Comparable[heap.length * 2]; for(int i = 0; i < heap.length; i++){ temp[i] = this.heap[i]; // Copy all the references } this.heap = temp; // Update instance backing array } Static sort method that sorts the passed in array in place using a heap. The sorted array is in ascending order. The passed in array must be full and not contain any null elements.
@param T[] a - the array of objects to be sorted in ascending order
@SuppressWarnings("unchecked") public static <T extends Comparable<? super T>> void sort(T[] a){ Heap12<T> sorted = new Heap12<T>(a); // Use unsorted array as heap // backing array in new Heap12 /* Add each array element to the heap, it will sort itself in place */ for(int i = 0; i < sorted.heap.length; i++) sorted.add(sorted.heap[sorted.size()]); // Size is initially 0 /* Remove each heap element, put it at the end of the underlying array */ while(sorted.size() > 0) sorted.heap[sorted.size() - 1] = sorted.remove(); } } 
