cornell.cs211
Class SortedHeap<E>

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

public class SortedHeap<E>
extends AbstractHeap<E>

The implementation of the heap using the sorted 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 methods top, pop, but O(n) for push, add methods.

Author:
Changxi Zheng

Field Summary
 
Fields inherited from class cornell.cs211.AbstractHeap
comparator
 
Constructor Summary
SortedHeap(java.util.List<E> list)
          Creates a SortedHeap that orders its elements according to their natural ordering (using Comparable).
SortedHeap(java.util.List<E> list, java.util.Comparator<? super E> comparator)
          Creates a SortedHeap 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)
          Insert the specified element into the heap.
 int size()
          Returns the current size.
static
<T> SortedHeap<T>
sortedArrayHeap(java.util.Comparator<? super T> comparator)
          Factory Method to create a SortedHeap using ArrayList with the specified comparator to determine the order in the heap
static
<T> SortedHeap<T>
sortedArrayHeap(T d)
          Factory Method to create a SortedHeap using ArrayList
static
<T> SortedHeap<T>
sortedListHeap(java.util.Comparator<? super T> comparator)
          Factory Method to create a SortedHeap using LinkedList with the specified comparator to determine the order in the heap
static
<T> SortedHeap<T>
sortedListHeap(T d)
          Factory Method to create a SortedHeap using LinkedList
 E top()
          Retrieves but doesn't remove the head of this heap, or null if this heap is empty.
 
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

SortedHeap

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


SortedHeap

public SortedHeap(java.util.List<E> list,
                  java.util.Comparator<? super E> comparator)
Creates a SortedHeap 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

sortedArrayHeap

public static <T> SortedHeap<T> sortedArrayHeap(T d)
Factory Method to create a SortedHeap using ArrayList


sortedListHeap

public static <T> SortedHeap<T> sortedListHeap(T d)
Factory Method to create a SortedHeap using LinkedList


sortedListHeap

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


sortedArrayHeap

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


push

public boolean push(E o)
Description copied from interface: Heap
Insert the specified element into the heap. This method is generally preferable to method Collection.add(E).

Parameters:
o - the element to insert
Returns:
true if it adds the element in the heap successfully, false otherwise.

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.

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>

iterator

public java.util.Iterator<E> iterator()
Returns an iterator over the elements in this heap.

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.