Max heap in Java

Question

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

• Marc-Andre: @Quonux Nice formatting! Turns out really great! I like the "javadoc" format!

Answer 1

One thing that I think need to be fixed is:

private Heap12(E[] e){
 this.heap = e; // Set heap array to passed in array
 this.size = 0; // Size HAS to be 0 initially
}

You need to copy it, otherwise the caller has reference to your array to corrupt it.

• sendi: my bad, i did not realize it was private.. too much intervention of comments in the middle

Answer 2

public class Heap12<E extends Comparable<? super E>> implements PQueue<E>{

Don't name your Generic Parameters with a single letter, give them meaningful names wit the end Type so you can differenciate between variables and the Generic Parameters when you read the code.

Do not name your class Heap12, it it a heap for only 12 elements or only for 12 monkeys... nobody knows.

private Heap12(E[] e){

Don't name your variables with single letters, give them meaningful names.

if(e == null) // Check for null element add
throw new NullPointerException();

The comment is not needed, describe why you do something and not what.

Here maybe a assertion is more useful (don't forget to enale assertions with the -ea Parameter, its realy a shame that its not on by default), oh tese poor rockets which exploded because of this... anyways back to topic

if(this.isEmpty()) // Empty heap case
return null;

the same as above, don't comment what your code does.

public boolean isEmpty(){
 return size == 0;
}

this is good, but we need also a method for the opposite

public boolean isNotEmpty(){
 return !this.isEmpty();
}

this makes reading of the code which uses this class easier.

swap(parent, child); // Swap them

again, the same, don't comment what the code does

• user2368778: Thanks. The name of the class was not by choice but I appreciate the feedback.