cornell.cs211
Class UnsortedHeap<E>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by cornell.cs211.AbstractHeap<E>
          extended by cornell.cs211.UnsortedHeap<E>
Type Parameters:
E - The type of the elements held in this collection.
All Implemented Interfaces:
Heap<E>, java.lang.Iterable<E>, java.util.Collection<E>

public class UnsortedHeap<E>
extends AbstractHeap<E>

The implementation of the heap using the unsorted list. The internal storage can be any list instances, i.e. linked list or array list

Implementation note: this implementation provides O(1) time for the insertion methods (push, add), but O(n) for remove(), top and pop methods.

Author:
Changxi Zheng

Field Summary
 
Fields inherited from class cornell.cs211.AbstractHeap
comparator
 
Constructor Summary
UnsortedHeap(java.util.List<E> list)
          Creates a UnsortedHeap that orders its elements according to their natural ordering (using Comparable).
UnsortedHeap(java.util.List<E> list, java.util.Comparator<? super E> comparator)
          Creates a UnsortedHeap that orders its elements according to the specified comparator.
 
Method Summary
 void clear()
          Removes all elements from the heap.
 java.util.Iterator<E> iterator()
          Returns an iterator over the elements in this heap.
 E pop()
          Retrieves and removes the head of this heap if exsits.
 boolean push(E o)
          Inserts the specified element into this heap.
 int size()
          Returns the current size.
 E top()
          Retrieves but doesn't remove the head of this heap, or null if this heap is empty.
static
<T> UnsortedHeap<T>
unsortedArrayHeap(java.util.Comparator<? super T> comparator)
          Factory Method to create a UnsortedHeap using ArrayList with the specified comparator to determine the order in the heap
static
<T> UnsortedHeap<T>
unsortedArrayHeap(T d)
          Factory Method to create a UnsortedHeap using ArrayList
static
<T> UnsortedHeap<T>
unsortedListHeap(java.util.Comparator<? super T> comparator)
          Factory Method to create a UnsortedHeap using LinkedList with the specified comparator to determine the order in the heap
static
<T> UnsortedHeap<T>
unsortedListHeap(T d)
          Factory Method to create a UnsortedHeap using LinkedList
 
Methods inherited from class cornell.cs211.AbstractHeap
add, addAll
 
Methods inherited from class java.util.AbstractCollection
contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray
 

Constructor Detail

UnsortedHeap

public UnsortedHeap(java.util.List<E> list)
Creates a UnsortedHeap that orders its elements according to their natural ordering (using Comparable).


UnsortedHeap

public UnsortedHeap(java.util.List<E> list,
                    java.util.Comparator<? super E> comparator)
Creates a UnsortedHeap that orders its elements according to the specified comparator.

Parameters:
comparator - the comparator used to order this heap. If null then the order depends on the elements' natural ordering.
Method Detail

unsortedArrayHeap

public static <T> UnsortedHeap<T> unsortedArrayHeap(T d)
Factory Method to create a UnsortedHeap using ArrayList


unsortedListHeap

public static <T> UnsortedHeap<T> unsortedListHeap(T d)
Factory Method to create a UnsortedHeap using LinkedList


unsortedListHeap

public static <T> UnsortedHeap<T> unsortedListHeap(java.util.Comparator<? super T> comparator)
Factory Method to create a UnsortedHeap using LinkedList with the specified comparator to determine the order in the heap


unsortedArrayHeap

public static <T> UnsortedHeap<T> unsortedArrayHeap(java.util.Comparator<? super T> comparator)
Factory Method to create a UnsortedHeap using ArrayList with the specified comparator to determine the order in the heap


push

public boolean push(E o)
Inserts the specified element into this heap. As this is a unsorted heap, the item is attached to the end of list. So the time complexity is O(1)

Parameters:
o - the element to insert
Returns:
true
Throws:
java.lang.ClassCastException - if the specified element cannot be compared with elements currently in the heap according to the heap's ordering.
java.lang.NullPointerException - if the specified element is null.

clear

public void clear()
Removes all elements from the heap. The heap will be empty after this call returns.

Specified by:
clear in interface java.util.Collection<E>
Overrides:
clear in class AbstractHeap<E>

size

public int size()
Returns the current size.

Specified by:
size in interface java.util.Collection<E>
Specified by:
size in class java.util.AbstractCollection<E>

top

public E top()
Description copied from interface: Heap
Retrieves but doesn't remove the head of this heap, or null if this heap is empty.

Returns:
the head of the heap, or null if this heap is empty.

pop

public E pop()
Description copied from interface: Heap
Retrieves and removes the head of this heap if exsits. Otherwise, do nothing and return null.

Returns:
the head of the heap, or null if this heap is empty.

iterator

public java.util.Iterator<E> iterator()
Returns an iterator over the elements in this heap. The iterator does not return the elements in any particular order.

Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.Collection<E>
Specified by:
iterator in class java.util.AbstractCollection<E>
Returns:
an iterator over the elements in this heap.