|
||||||||||
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.PairingHeap<E>
public class PairingHeap<E>
The pairing heap is a simple
self-organizing data structure in which the
amortized cost for add
, merge
, and
remove
through a tracker are all logarithmic.
The insert and merge methods have worst-case constant cost.
When an element is removed, the data structure is re-structured,
leading to a worst-case linear cost.
Increasing the priority for a tracked element has worst-case
constant cost, but the amortized cost of this operation is
logarithmic due to an increase in the potential. Intuitively,
each add
method is charged to compensate for the future
reorganization cost. To decrease the priority of a tracked element,
the amortized cost is logarithmic, although the worst-case cost
is linear. The space usage of the pairing heap is
similar to that of the leftist heap. While we provide only
a threaded version of a pairing heap,
a non-threaded version could be created as illustrated in the leftist
heap implementation.
Nested Class Summary | |
---|---|
protected class |
PairingHeap.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, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
PairingHeap()
|
|
PairingHeap(Comparator<? super E> comp)
|
Method Summary | |
---|---|
void |
add(E element)
Adds it to the heap |
PriorityQueueLocator<E> |
addTracked(E element)
Inserts o into
the collection in an arbitrary location and returns
a tracker to the inserted element. |
E |
extractMax()
Removes and returns a highest priority 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 . |
PriorityQueueLocator<E> |
iterator()
Creates a new tracker that is at FORE. |
E |
max()
Returns a highest priority element. |
boolean |
remove(E element)
Removes an equivalent element from the collection |
String |
showStructure()
|
protected void |
update(goldman.collection.priority.PairingHeap.HeapNode<E> x,
E element)
|
Methods inherited from class goldman.collection.AbstractCollection |
---|
accept, addAll, checkRep, clear, compare, contains, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, 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, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
---|
accept, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public PairingHeap()
public PairingHeap(Comparator<? super E> comp)
comp
- a user-provided comparatorMethod Detail |
---|
public E max()
PriorityQueue
NoSuchElementException
when this collection is empty.
max
in interface PriorityQueue<E>
NoSuchElementException
- this pairing heap is emptypublic 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)
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
protected void update(goldman.collection.priority.PairingHeap.HeapNode<E> x, E element)
x
- a reference a node holding the element to be replacedelement
- the replacement element
x
is not nullpublic boolean remove(E element)
remove
in interface Collection<E>
element
- the target
public E extractMax()
PriorityQueue
NoSuchElementException
when this collection is empty.
extractMax
in interface PriorityQueue<E>
NoSuchElementException
- the collection is empty.public PriorityQueueLocator<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 |