|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.priority.BinaryHeap<E>
public class BinaryHeap<E>
The binary heap is a very simple data structure
that has worst-case logarithmic
cost for add
, extractMax
, and update
(through
a locator). However, the lead constant within the asymptotic notation
is small, so all of the methods run quite quickly. Also the space usage
is very efficient, especially if the required size is passed to the constructor.
The main drawback is that merging two binary heaps takes linear time.
Also, increasing
the priority of a tracked element takes logarithmic time.
Nested Class Summary | |
---|---|
class |
BinaryHeap.BinaryHeapLocator
|
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection |
---|
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator |
Field Summary |
---|
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, FORE, size, version |
Constructor Summary | |
---|---|
BinaryHeap()
Creates an empty priority queue that uses the default comparator |
|
BinaryHeap(boolean tracked)
Creates a tracked or untracked empty priority queue depending on whether tracked is true or false. |
|
BinaryHeap(Comparator<? super E> comp)
Creates an untracked empty priority queue that orders the elements using the provided comparator, and has a default initial capacity |
|
BinaryHeap(int initialCapacity)
Creates an empty untracked empty priority queue that uses the default comparator, and the provided initial capacity. |
|
BinaryHeap(int initialCapacity,
Comparator<? super E> comp)
Creates an untracked empty priority queue that uses the provided initial capacity and comparator. |
|
BinaryHeap(int initialCapacity,
Comparator<? super E> comp,
boolean tracked)
It creates an empty priority queue with the specified characteristics. |
Method Summary | |
---|---|
void |
add(E element)
Inserts value into
the collection in an arbitrary location. |
void |
addAll(Collection<? extends E> c)
Adds all elements in c to the collection. |
PriorityQueueLocator<E> |
addTracked(E element)
Inserts o into
the collection in an arbitrary location and returns
a tracker to the inserted element. |
void |
clear()
Removes all elements from the collection |
boolean |
contains(E element)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
E |
extractMax()
Removes and returns a highest priority element. |
protected int |
find(E element)
|
E |
getEquivalentElement(E target)
Returns an element in the collection that is equivalent to target . |
PriorityQueueLocator<E> |
getLocator(E element)
This method runs in worst-case linear time. |
int |
getSize()
Returns the number of elements, size, in this collection. |
boolean |
isEmpty()
Returns true if this collection contains no elements, and otherwise returns false. |
PriorityQueueLocator<E> |
iterator()
Creates a new locator that is at FORE. |
E |
max()
Returns a highest priority element. |
boolean |
remove(E target)
Removes from the collection an arbitrary element (if any) equivalent to the target. |
protected void |
remove(int p)
|
void |
retainAll(Collection<E> c)
Updates the current collection to contain only elements that are also in c |
boolean |
supportsTracking()
|
protected void |
update(int p,
E element)
|
Methods inherited from class goldman.collection.AbstractCollection |
---|
accept, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Methods inherited from interface goldman.collection.Collection |
---|
accept, checkRep, ensureCapacity, getCapacity, getComparator, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
---|
accept, checkRep, ensureCapacity, getCapacity, getComparator, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public BinaryHeap(int initialCapacity, Comparator<? super E> comp, boolean tracked)
initialCapacity
- the desired initial
capacitycomp
- a user-provided
comparator that defines the ordering among the elementstracked
- to indicate
whether or not tracking should be supported.public BinaryHeap()
public BinaryHeap(Comparator<? super E> comp)
comp
- a user-provided
comparatorpublic BinaryHeap(int initialCapacity)
initialCapacity
- the desired initial
capacitypublic BinaryHeap(int initialCapacity, Comparator<? super E> comp)
initialCapacity
- the desired initial
capacitycomp
- a user-provided comparatorpublic BinaryHeap(boolean tracked)
tracked
is true or false. The priority queue is
created with the default comparator, and has a default initial capacity
tracked
- to indicate whether
tracking is desiredMethod Detail |
---|
public boolean supportsTracking()
public int getSize()
Collection
getSize
in interface Collection<E>
getSize
in class AbstractCollection<E>
public boolean isEmpty()
Collection
isEmpty
in interface Collection<E>
isEmpty
in class AbstractCollection<E>
public E max()
PriorityQueue
NoSuchElementException
when this collection is empty.
max
in interface PriorityQueue<E>
NoSuchElementException
- this collection is emptyprotected int find(E element)
element
- the target
public boolean contains(E element)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
element
- the target
public E getEquivalentElement(E target)
Collection
target
. It
throws a NoSuchElementException
when there is no equivalent
element. The contains
method should be used to
determine if an element is in the collection.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in class AbstractCollection<E>
target
- the target element
protected void update(int p, E element)
p
- the position of the element to updateelement
- the replacement element
size
public void add(E element)
Collection
value
into
the collection in an arbitrary location. If a tracker is to be returned
then the method addTracked
which is part of the
Tracked
interface should be called instead.
An AtCapacityException
(an unchecked exception) is thrown when a bounded
collection is already at capacity.
add
in interface Collection<E>
element
- the element to addpublic PriorityQueueLocator<E> addTracked(E element)
Tracked
o
into
the collection in an arbitrary location and returns
a tracker to the inserted element.
An AtCapacityException
(an unchecked exception) is thrown if the
collection is already at capacity.
addTracked
in interface Tracked<E>
element
- the element
to add
UnsupportedOperationException
- tracking is not being
supported, as specified in the constructor callpublic void addAll(Collection<? extends E> c)
AbstractCollection
c
to the collection.
addAll
in interface Collection<E>
addAll
in class AbstractCollection<E>
c
- the collection to be added to this collectionpublic E extractMax()
PriorityQueue
NoSuchElementException
when this collection is empty.
extractMax
in interface PriorityQueue<E>
NoSuchElementException
- called on an empty collection.protected void remove(int p)
p
- the position
of the element to remove
size
public boolean remove(E target)
remove
in interface Collection<E>
target
- the element to remove
true
if an element was removed, and false
otherwise.public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public void retainAll(Collection<E> c)
c
retainAll
in interface Collection<E>
retainAll
in class AbstractCollection<E>
c
- a collectionpublic PriorityQueueLocator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public PriorityQueueLocator<E> getLocator(E element)
getLocator
in interface Collection<E>
getLocator
in interface PriorityQueue<E>
element
- the target
NoSuchElementException
- there is no equivalent element
in this collection.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |