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

}
  • @Quonux Nice formatting! Turns out really great! I like the "javadoc" format! – Marc-Andre Aug 29 '13 at 13:27
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

  • Thanks. The name of the class was not by choice but I appreciate the feedback. – user2368778 Jul 31 '13 at 4:58

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.

  • my bad, i did not realize it was private.. too much intervention of comments in the middle – sendi Jun 3 at 22:47

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.