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();
}
}
