|
|||||||||
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.UnsortedHeap<E>
E
- The type of the elements held in this collection.public class UnsortedHeap<E>
The implementation of the heap using the unsorted 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 insertion methods (push, add), but O(n) for remove(), top and pop methods.
Field Summary |
---|
Fields inherited from class cornell.cs211.AbstractHeap |
---|
comparator |
Constructor Summary | |
---|---|
UnsortedHeap(java.util.List<E> list)
Creates a UnsortedHeap that orders its elements according to their natural ordering (using Comparable). |
|
UnsortedHeap(java.util.List<E> list,
java.util.Comparator<? super E> comparator)
Creates a UnsortedHeap 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. |
|
static
|
unsortedArrayHeap(java.util.Comparator<? super T> comparator)
Factory Method to create a UnsortedHeap using ArrayList with the specified comparator to determine the order in the heap |
|
static
|
unsortedArrayHeap(T d)
Factory Method to create a UnsortedHeap using ArrayList |
|
static
|
unsortedListHeap(java.util.Comparator<? super T> comparator)
Factory Method to create a UnsortedHeap using LinkedList with the specified comparator to determine the order in the heap |
|
static
|
unsortedListHeap(T d)
Factory Method to create a UnsortedHeap using LinkedList |
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 UnsortedHeap(java.util.List<E> list)
public UnsortedHeap(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> UnsortedHeap<T> unsortedArrayHeap(T d)
public static <T> UnsortedHeap<T> unsortedListHeap(T d)
public static <T> UnsortedHeap<T> unsortedListHeap(java.util.Comparator<? super T> comparator)
public static <T> UnsortedHeap<T> unsortedArrayHeap(java.util.Comparator<? super T> comparator)
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()
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 |