
Cytoscape 2.8.0 API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object cytoscape.util.intr.MinIntHeap
public final class MinIntHeap
A heap is an implementation of a priority queue. A priority queue is a special kind of queue where the next value on the queue is the least element in the queue. A heap can be used to order N elements in O(n*log(N)) time complexity. Because of some of the propeties of a heap, heaps are especially good at returning the M least elements from a set of N elements, where M < N. In particular, if M is constrained to be [less than or] equal to N/log_{2}(N) [as N varies] then the first M least elements from a set of N elements can be computed in O(N) time complexity (linear time).
A heap can have two states: ordered and unordered. The time complexity of certain operations is dependent on the state of the heap. Certain operations will effect the state of the heap. Please read the documentation of each method to better understand the time complexity of each operation and the operation's relationship to the state of the heap.
An instance of this class is serializable; however, serialized instances of this class should not be stored in a persistent manner because the serialization implemented in this class makes no attempt at handling class versioning.
Constructor Summary  

MinIntHeap()
Creates a new heap. 
Method Summary  

void 
copyInto(int[] output,
int beginIndex)
Deprecated. Use elements() instead. 
void 
copyIntoReverseOrder(int[] output,
int beginIndex)
Deprecated. Use orderedElements(boolean) or deleteMin() instead. 
int 
deleteMin()
Deletes and returns the minimum element in this heap. 
IntEnumerator 
elements()
Returns an enumeration over all the elements currently in this heap; the order of elements in the returned enumeration is undefined. 
void 
empty()
Empties this heap of all elements. 
int 
findMin()
Returns the minimum element in this heap. 
void 
insert(int x)
If this heap is ordered prior to calling this operation, adds specified element to heap such that the heap will remain ordered after this operation, taking O(log(N)) time where N is the number of elements in this heap (average time is actually constant regardless of size of heap). 
boolean 
isOrdered()
Returns true if and only if the heap is currently ordered. 
IntEnumerator 
orderedElements(boolean pruneDuplicates)
Returns an enumeration of elements in this heap, ordered such that the least element is first in the returned enumeration. 
int 
size()
Returns the number of elements currently in this heap. 
void 
toss(int x)
Tosses a new element onto the heap. 
void 
toss(int[] elements,
int beginIndex,
int length)
Tosses a bunch of new elements onto the heap at once. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 

public MinIntHeap()
Method Detail 

public final void empty()
public final int size()
public final boolean isOrdered()
public final void toss(int x)
public final void toss(int[] elements, int beginIndex, int length)
elements
 an array containing elements to be tossed onto this heap.beginIndex
 the index in the elements array from which to start
tossing elements onto this heap.length
 the number of contiguous elements in the elements array
to toss onto this heap.
IndexOutOfBoundsException
 if the combination of the
input parameters (elements, beginIndex, and length) don't make sense.public final void insert(int x)
If the underlying data structure is not large enough to hold an additional element, the structure is made larger; the process of making the underlying structure larger takes O(N) time; the enlargening operation doubles the size of the underlying structure. Therefore, the time complexities described above are amortized time complexities.
public final int findMin()
If there are no elements in this heap, results of this operation are undefined.
public final int deleteMin()
If there are no elements in this heap, results of this operation are undefined.
public final IntEnumerator orderedElements(boolean pruneDuplicates)
If pruneDuplicates is false, this method returns in constant time, unless this heap is unordered when this method is called, in which case this method returns in O(N) time. The returned enumeration takes O(log(N)) time complexity to return each successive element.
If pruneDuplicates is true, this method takes O(N*log(N)) time complexity to come up with the return value regardless of whether or not this heap is in an ordered state at the time this method is called. (Truth be told, this method will come up with a return value in less time if this heap is in an ordered state when this method is called.) The retuned enumeration takes constant time to return each successive element.
The returned enumeration becomes invalid as soon as any other method on this heap instance is called; calling methods on an invalid enumeration will cause undefined behavior in both the enumerator and in the underlying heap.
Calling this function automatically causes this heap to become unordered. No elements are added or removed from this heap as a result of using the returned enumeration.
elements()
public final IntEnumerator elements()
If other methods in this heap are called while enumerating through the return value, behavior of the enumerator is undefined.
This enumerator has no effect on the set of elements in this heap. This enumeration has no effect on the ordered state of this heap.
orderedElements(boolean)
public final void copyInto(int[] output, int beginIndex)
NOTE: This method has been deprecated ever since it was added to this class. A decision is being made as to whether or not to keep this method.
output
 the array into which the elements of this heap get copied.beginIndex
 an index in the output array which is the beginning
of where elements are copied to.
IndexOutOfBoundsException
 if copying would cause access of
data outside output array bounds.elements()
public final void copyIntoReverseOrder(int[] output, int beginIndex)
This operation takes O(N*log(N)) time complexity, regardless of whether or not this heap is in an ordered state at the time this method is called. (Truth be told, this method will be faster if the heap is in an ordered state when this method is called.) This operation also leaves this heap in an unordered state. No elements are added or removed from this heap as a result of using this operation.
NOTE: This method has been deprecated ever since it was added to this class. A decision is being made as to whether or not to keep this method.
output
 the array into which the elements of this heap get copied.beginIndex
 an index in the output array which is the beginning
of where elements are copied to.
IndexOutOfBoundsException
 if copying would cause access of
data outside output array bounds.orderedElements(boolean)
,
deleteMin()

Cytoscape 2.8.0 API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 