|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectjava.util.AbstractCollection<E>
cornell.cs211.AbstractHeap<E>
cornell.cs211.StdHeap<E>
E - The type of the elements held in this collection.public class StdHeap<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).
| 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 |
|---|
public StdHeap()
public StdHeap(int initCapacity,
java.util.Comparator<? super E> comparator)
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.
java.lang.IllegalArgumentException - if initialCapacity is less
than 1| Method Detail |
|---|
public boolean push(E o)
o - the element to insert
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.public void clear()
clear in interface java.util.Collection<E>clear in class AbstractHeap<E>public int size()
size in interface java.util.Collection<E>size in class java.util.AbstractCollection<E>public E top()
Heap
public E pop()
Heap
public java.util.Iterator<E> iterator()
Currently, The iterator doesn't support remove method, since it is a optional in Iterable interface.
iterator in interface java.lang.Iterable<E>iterator in interface java.util.Collection<E>iterator in class java.util.AbstractCollection<E>
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||