cytoscape.util.intr
Class MinIntHeap

java.lang.Object
  cytoscape.util.intr.MinIntHeap

All Implemented Interfaces:

Serializable

public final class MinIntHeap
extends Object
implements Serializable

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₂(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.

See Also:

Serialized Form

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

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinIntHeap

public MinIntHeap()

Creates a new heap. A new heap is ordered.

Method Detail

empty

public final void empty()

Empties this heap of all elements. The heap is ordered after this operation.

size

public final int size()

Returns the number of elements currently in this heap.

isOrdered

public final boolean isOrdered()

Returns true if and only if the heap is currently ordered.

toss

public final void toss(int x)

Tosses a new element onto the heap. The heap will be become unordered after this operation; this operation takes constant [amortized] time.

toss

public final void toss(int[] elements,
                       int beginIndex,
                       int length)

Tosses a bunch of new elements onto the heap at once. The heap will become unordered after this operation; this operation takes O(N) time where N is the number of elements being tossed onto the heap.

Parameters:

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.

Throws:

IndexOutOfBoundsException - if the combination of the input parameters (elements, beginIndex, and length) don't make sense.

insert

public final 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). If this heap is not ordered when this operation is called, adds specified element to heap in constant time.

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.

findMin

public final int findMin()

Returns the minimum element in this heap. This is a constant time operation if the heap is ordered. If the heap is not ordered, this operation will first order the entire heap. The time complexity of ordering an unordered heap is O(N) where N is the number of elements in the heap. This method leaves the heap in an ordered state.

If there are no elements in this heap, results of this operation are undefined.

deleteMin

public final int deleteMin()

Deletes and returns the minimum element in this heap. This operation has time complexity O(log(N)) where N is the number of elements currently in this heap, assuming that the heap is ordered. If the heap is not ordered at the time this operation is invoked, this operation will first order the entire heap. The time complexity of ordering an unordered heap is O(N), where N is the number of elements in the heap. When this method returns, this heap is in an ordered state.

If there are no elements in this heap, results of this operation are undefined.

orderedElements

public final IntEnumerator orderedElements(boolean pruneDuplicates)

Returns an enumeration of elements in this heap, ordered such that the least element is first in the returned enumeration. Pruning of duplicate elements is enabled by setting pruneDuplicates to true.

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.

See Also:

elements()

elements

public final IntEnumerator elements()

Returns an enumeration over all the elements currently in this heap; the order of elements in the returned enumeration is undefined.

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.

See Also:

orderedElements(boolean)

copyInto

public final void copyInto(int[] output,
                           int beginIndex)

Deprecated. Use elements() instead.

Copies the elements of this heap into the specified output array. The order in which elements are copied is undefined. Elements are copied into the output array starting at beginIndex in the output array. The output array must be large enough to hold all the elements in this heap.

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.

Parameters:

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.

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside output array bounds.

See Also:

elements()

copyIntoReverseOrder

public final void copyIntoReverseOrder(int[] output,
                                       int beginIndex)

Deprecated. Use orderedElements(boolean) or deleteMin() instead.

Copies the elements of this heap into the specified output array in descending order. The largest element (the largest integer, that is) in this heap is placed at index beginIndex in the output array. The smallest element in this heap is placed at index beginIndex+size()-1 in the output array. The output array must be large enough to hold all the elements in this heap.

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.

Parameters:

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.

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside output array bounds.

See Also:

orderedElements(boolean), deleteMin()