cornell.cs211
Class StdHeap<E>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by cornell.cs211.AbstractHeap<E>
          extended by cornell.cs211.StdHeap<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 StdHeap<E>
extends AbstractHeap<E>

The standard implementation of the heap, which is very similar with java.util.PriorityQueue, using the binary serach tree (BST).

The BST used in this class is

Implementation note: this implementation provides O(log(n)) time for the insertion methods (push, pop, remove() and add) methods; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

Author:
Changxi Zheng

Field Summary
 
Fields inherited from class cornell.cs211.AbstractHeap
comparator
 
Constructor Summary
StdHeap()
          Creates a StdHeap with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable).
StdHeap(int initCapacity, java.util.Comparator<? super E> comparator)
          Creates a StdHeap with the specified initial capacity 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.
 
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

StdHeap

public StdHeap()
Creates a StdHeap with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable).


StdHeap

public StdHeap(int initCapacity,
               java.util.Comparator<? super E> comparator)
Creates a StdHeap with the specified initial capacity that orders its elements according to the specified comparator.

Parameters:
initCapacity - the initial capacity for this heap.
comparator - the comparator used to order this heap. If null then the order depends on the elements' natural ordering.
Throws:
java.lang.IllegalArgumentException - if initialCapacity is less than 1
Method Detail

push

public boolean push(E o)
Inserts the specified element into this heap.

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.

Currently, The iterator doesn't support remove method, since it is a optional in Iterable interface.

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.