|
|||||||||
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 1Method 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 |