|
|||||||||
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.SortedHeap<E>
E
- The type of the elements held in this heap.public class SortedHeap<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.
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
|
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
|
sortedArrayHeap(T d)
Factory Method to create a SortedHeap using ArrayList |
|
static
|
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
|
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 |
---|
public SortedHeap(java.util.List<E> list)
public SortedHeap(java.util.List<E> list, java.util.Comparator<? super E> comparator)
comparator
- the comparator used to order this heap.
If null then the order depends on the elements' natural
ordering.Method Detail |
---|
public static <T> SortedHeap<T> sortedArrayHeap(T d)
public static <T> SortedHeap<T> sortedListHeap(T d)
public static <T> SortedHeap<T> sortedListHeap(java.util.Comparator<? super T> comparator)
public static <T> SortedHeap<T> sortedArrayHeap(java.util.Comparator<? super T> comparator)
public boolean push(E o)
Heap
Collection.add(E)
.
o
- the element to insert
public E top()
Heap
public E pop()
Heap
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 java.util.Iterator<E> iterator()
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 |