goldman.collection.priority
Class BinaryHeap<E>

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

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

BinaryHeap

public BinaryHeap(int initialCapacity,
                  Comparator<? super E> comp,
                  boolean tracked)
It creates an empty priority queue with the specified characteristics.

Parameters:
initialCapacity - the desired initial capacity
comp - a user-provided comparator that defines the ordering among the elements
tracked - to indicate whether or not tracking should be supported.

BinaryHeap

public BinaryHeap()
Creates an empty priority queue that uses the default comparator


BinaryHeap

public 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

Parameters:
comp - a user-provided comparator

BinaryHeap

public BinaryHeap(int initialCapacity)
Creates an empty untracked empty priority queue that uses the default comparator, and the provided initial capacity.

Parameters:
initialCapacity - the desired initial capacity

BinaryHeap

public BinaryHeap(int initialCapacity,
                  Comparator<? super E> comp)
Creates an untracked empty priority queue that uses the provided initial capacity and comparator.

Parameters:
initialCapacity - the desired initial capacity
comp - a user-provided comparator

BinaryHeap

public BinaryHeap(boolean tracked)
Creates a tracked or untracked empty priority queue depending on whether tracked is true or false. The priority queue is created with the default comparator, and has a default initial capacity

Parameters:
tracked - to indicate whether tracking is desired
Method Detail

supportsTracking

public boolean supportsTracking()

getSize

public int getSize()
Description copied from interface: Collection
Returns the number of elements, size, in this collection.

Specified by:
getSize in interface Collection<E>
Overrides:
getSize in class AbstractCollection<E>
Returns:
the number of elements stored in the collection

isEmpty

public boolean isEmpty()
Description copied from interface: Collection
Returns true if this collection contains no elements, and otherwise returns false.

Specified by:
isEmpty in interface Collection<E>
Overrides:
isEmpty in class AbstractCollection<E>
Returns:
true if and only if no elements are stored in the collection

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 collection is empty

find

protected int 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.

contains

public boolean contains(E element)
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:
element - the target
Returns:
true if and only if an equivalent element exists 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 that is in the collection

update

protected void update(int p,
                      E element)
Parameters:
p - the position of the element to update
element - the replacement element
REQUIRES: 0 ≤ p < size

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
Throws:
UnsupportedOperationException - tracking is not being supported, as specified in the constructor call

addAll

public void addAll(Collection<? extends E> c)
Description copied from class: AbstractCollection
Adds all elements in c to the collection.

Specified by:
addAll in interface Collection<E>
Overrides:
addAll in class AbstractCollection<E>
Parameters:
c - the collection to be added to this collection

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:
the highest priority element from the collection
Throws:
NoSuchElementException - called on an empty collection.

remove

protected void remove(int p)
Parameters:
p - the position of the element to remove
REQUIRES: 0 ≤ p < size

remove

public boolean remove(E target)
Removes from the collection an arbitrary element (if any) equivalent to the target.

Specified by:
remove in interface Collection<E>
Parameters:
target - the element to remove
Returns:
true if an element was removed, and false otherwise.

clear

public void clear()
Removes all elements from the collection

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

retainAll

public void retainAll(Collection<E> c)
Updates the current collection to contain only elements that are also in c

Specified by:
retainAll in interface Collection<E>
Overrides:
retainAll in class AbstractCollection<E>
Parameters:
c - a collection

iterator

public PriorityQueueLocator<E> iterator()
Creates a new locator 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)
This method runs in worst-case linear time.

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