goldman.collection.priority
Class PairingHeap<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.priority.PairingHeap<E>
All Implemented Interfaces:
Collection<E>, PriorityQueue<E>, Tracked<E>, Iterable<E>
Direct Known Subclasses:
FibonacciHeap

public class PairingHeap<E>
extends AbstractCollection<E>
implements PriorityQueue<E>, Tracked<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

PairingHeap

public PairingHeap()

PairingHeap

public PairingHeap(Comparator<? super E> comp)
Parameters:
comp - a user-provided comparator
Method Detail

max

public E max()
Description copied from interface: PriorityQueue
Returns a highest priority element. It throws a NoSuchElementException when this collection is empty.

Specified by:
max in interface PriorityQueue<E>
Returns:
a highest priority element
Throws:
NoSuchElementException - this pairing heap is empty

getEquivalentElement

public E getEquivalentElement(E target)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to 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.

Specified by:
getEquivalentElement in interface Collection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
target - the target element
Returns:
an equivalent element
Throws:
NoSuchElementException - there is no equivalent element in this collection.

add

public void add(E element)
Adds it to the heap

Specified by:
add in interface Collection<E>
Parameters:
element - the element to add

addTracked

public PriorityQueueLocator<E> addTracked(E element)
Description copied from interface: Tracked
Inserts 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.

Specified by:
addTracked in interface Tracked<E>
Parameters:
element - the element to add
Returns:
a tracker to the newly added element

update

protected void update(goldman.collection.priority.PairingHeap.HeapNode<E> x,
                      E element)
Parameters:
x - a reference a node holding the element to be replaced
element - the replacement element
REQUIRES: x is not null

remove

public boolean remove(E element)
Removes an equivalent element from the collection

Specified by:
remove in interface Collection<E>
Parameters:
element - the target
Returns:
true if and only if an equivalent element was found, and hence removed

extractMax

public E extractMax()
Description copied from interface: PriorityQueue
Removes and returns a highest priority element. It throws a NoSuchElementException when this collection is empty.

Specified by:
extractMax in interface PriorityQueue<E>
Returns:
and removes the highest priority element from the collection
Throws:
NoSuchElementException - the collection is empty.

iterator

public PriorityQueueLocator<E> iterator()
Creates a new tracker that is at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

getLocator

public PriorityQueueLocator<E> getLocator(E element)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to 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.

Specified by:
getLocator in interface Collection<E>
Specified by:
getLocator in interface PriorityQueue<E>
Parameters:
element - the target
Returns:
a tracker positioned at the given element.
Throws:
NoSuchElementException - there is no equivalent element in this collection.

showStructure

public String showStructure()