goldman.collection.priority
Class LeftistHeap<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.priority.LeftistHeap<E>
All Implemented Interfaces:
Collection<E>, PriorityQueue<E>, Tracked<E>, Iterable<E>

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

LeftistHeap

public LeftistHeap()

LeftistHeap

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

LeftistHeap

public LeftistHeap(LeftistHeap<E> h1,
                   LeftistHeap<E> h2)
Parameters:
h1 - a leftist heap
h2 - a leftist heap
Throws:
IllegalArgumentException - h1 and h2 do not use the same comparator
Method Detail

contains

protected boolean contains(E target,
                           goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> x)
Parameters:
target - the target value
x - the root of the subtree to search
Returns:
true if and only if T(x) contains an element equivalent to the target.

contains

public boolean contains(E target)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
target - the target value
Returns:
true when there is an equivalent element to the target in this collection. Otherwise, false is returned.

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 leftist heap is empty

traverseForVisitor

protected void traverseForVisitor(Visitor<? super E> v)
                           throws Exception
Applies the visitor from the root of the leftist heap

Overrides:
traverseForVisitor in class AbstractCollection<E>
Parameters:
v - the visitor
Throws:
Exception

writeElements

protected void writeElements(StringBuilder sb)
The method appends each item's string representation to the string buffer, separated by commas.

Overrides:
writeElements in class AbstractCollection<E>
Parameters:
sb - a string buffer in which to create a string representation of the collection

find

protected goldman.collection.priority.LeftistHeap.LeftistHeapNode<E> find(E element)
Parameters:
element - the target
Returns:
a reference to a heap node holding an equivalent element, or null\ if there is no equivalent element in this collection

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)
Description copied from interface: Collection
Inserts 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.

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

remove

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

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

extractMax

public E extractMax()
This method also removes the maximum priority element from the collection.

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

clear

public void clear()
Removes all elements from the collection

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

iterator

public Locator<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()