|
||||||||||
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.LeftistHeap<E>
public class LeftistHeap<E>
The leftist heap is a fairly simple
implementation that supports merge
in logarithmic time.
A leftist heap can be threaded to support faster iteration, or
non-threaded. We provide only a non-threaded leftist heap implementation,
but a threaded version could be implemented
as illustrated for a pairing heap.
The primary cost of the threading would be the increased space due to
two additional
references per element. There would also be a small amount of overhead required to
maintain the extra references. In the threaded implementation, all of the methods
would have the same time complexity as for the binary heap, except
for merge
which is improved from linear to logarithmic time, and
addAll
which changes from constant time per new element to
logarithmic time per new element. In the non-threaded implementation,
iteration is limited and less efficient than the threaded implementation.
Nested Class Summary | |
---|---|
protected class |
LeftistHeap.Tracker
|
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, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
LeftistHeap()
|
|
LeftistHeap(Comparator<? super E> comp)
|
|
LeftistHeap(LeftistHeap<E> h1,
LeftistHeap<E> h2)
|
Method Summary | |
---|---|
void |
add(E element)
Inserts value into
the collection in an arbitrary location. |
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 target)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
protected boolean |
contains(E target,
goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> x)
|
E |
extractMax()
This method also removes the maximum priority element from the collection. |
protected goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> |
find(E element)
|
E |
getEquivalentElement(E target)
Returns an element in the collection that is equivalent to target . |
PriorityQueueLocator<E> |
getLocator(E element)
Returns a locator that has been initialized to an element equivalent to target . |
Locator<E> |
iterator()
Creates a new tracker that is at FORE. |
E |
max()
Returns a highest priority element. |
boolean |
remove(E target)
Removes an equivalent element from the collection |
String |
showStructure()
|
protected void |
traverseForVisitor(Visitor<? super E> v)
Applies the visitor from the root of the leftist heap |
protected void |
writeElements(StringBuilder sb)
The method appends each item's string representation to the string buffer, separated by commas. |
Methods inherited from class goldman.collection.AbstractCollection |
---|
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
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, addAll, checkRep, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
---|
accept, addAll, checkRep, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public LeftistHeap()
public LeftistHeap(Comparator<? super E> comp)
comp
- a user-provided
comparatorpublic LeftistHeap(LeftistHeap<E> h1, LeftistHeap<E> h2)
h1
- a leftist heaph2
- a leftist heap
IllegalArgumentException
- h1
and h2
do not use the same comparatorMethod Detail |
---|
protected boolean contains(E target, goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> x)
target
- the target valuex
- the root of the subtree to search
public boolean contains(E target)
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>
target
- the target value
public E max()
PriorityQueue
NoSuchElementException
when this collection is empty.
max
in interface PriorityQueue<E>
NoSuchElementException
- this leftist heap is emptyprotected void traverseForVisitor(Visitor<? super E> v) throws Exception
traverseForVisitor
in class AbstractCollection<E>
v
- the visitor
Exception
protected void writeElements(StringBuilder sb)
writeElements
in class AbstractCollection<E>
sb
- a string buffer in which to create a string representation of the collectionprotected goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> find(E element)
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
NoSuchElementException
- there is no equivalent element in this
collection.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
public boolean remove(E target)
remove
in interface Collection<E>
target
- the element to remove
public E extractMax()
extractMax
in interface PriorityQueue<E>
NoSuchElementException
- the collection is empty.public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public PriorityQueueLocator<E> getLocator(E element)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
getLocator
in interface PriorityQueue<E>
element
- the target
NoSuchElementException
- there is no equivalent element
in this collection.public String showStructure()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |