Progeneric.Ptl.Algorithms

Class HeapOper

java.lang.Object

Progeneric.Ptl.Algorithms.HeapOper

public final class HeapOper
extends java.lang.Object

Implements basic operations of a heap data structure that has two properties: The first element is always the largest. Elements may be added or removed in logarithmic time.

Method Summary

Methods

Modifier and Type	Method and Description
static <T extends java.lang.Comparable<T>> boolean	IsHeap(T[] x, int first, int last) Tests whether the input range is a heap.
static <T> boolean	IsHeap(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.
static <T extends java.lang.Comparable<T>,TBidIter extends IBidIter<T,TBidIter>> boolean	IsHeap(TBidIter first, TBidIter last) Tests whether the input range is a heap.
static <T,TBidIter extends IBidIter<T,TBidIter>> boolean	IsHeap(TBidIter first, TBidIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.
static <T extends java.lang.Comparable<T>> int	IsHeapUntil(T[] x, int first, int last) Tests whether the input range is a heap.
static <T> int	IsHeapUntil(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.
static <T extends java.lang.Comparable<T>,TBidIter extends IBidIter<T,TBidIter>> TBidIter	IsHeapUntil(TBidIter first, TBidIter last) Tests whether the input range is a heap.
static <T,TBidIter extends IBidIter<T,TBidIter>> TBidIter	IsHeapUntil(TBidIter first, TBidIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.
static <T extends java.lang.Comparable<T>> void	MakeHeap(T[] x, int first, int last) Converts elements from a specified range into a heap in which the first element is the largest.
static <T> void	MakeHeap(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion is specified with a binary predicate.
static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void	MakeHeap(TRanIter first, TRanIter last) Converts elements from a specified range into a heap in which the first element is the largest.
static <T,TRanIter extends IRanIter<T,TRanIter>> void	MakeHeap(TRanIter first, TRanIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion is specified with a binary predicate.
static <T extends java.lang.Comparable<T>> void	PopHeap(T[] x, int first, int last) Removes the largest element from the heap and then forms a new heap from the remaining elements.
static <T> void	PopHeap(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Removes the largest element from the heap and then forms a new heap from the remaining elements.
static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void	PopHeap(TRanIter first, TRanIter last) Removes the largest element from the heap and then forms a new heap from the remaining elements.
static <T,TRanIter extends IRanIter<T,TRanIter>> void	PopHeap(TRanIter first, TRanIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Removes the largest element from the heap and then forms a new heap from the remaining elements.
static <T extends java.lang.Comparable<T>> void	PushHeap(T[] x, int first, int last) Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.
static <T> void	PushHeap(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.
static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void	PushHeap(TRanIter first, TRanIter last) Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.
static <T,TRanIter extends IRanIter<T,TRanIter>> void	PushHeap(TRanIter first, TRanIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.
static <T extends java.lang.Comparable<T>> void	SortHeap(T[] x, int first, int last) Converts a heap into a sorted range.
static <T> void	SortHeap(T[] x, int first, int last, IFunc2Arg<T,T,java.lang.Boolean> pred) Converts a heap into a sorted range.
static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void	SortHeap(TRanIter first, TRanIter last) Converts a heap into a sorted range.
static <T,TRanIter extends IRanIter<T,TRanIter>> void	SortHeap(TRanIter first, TRanIter last, IFunc2Arg<T,T,java.lang.Boolean> pred) Converts a heap into a sorted range.

Methods inherited from class java.lang.Object

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

Method Detail

IsHeap

public static <T extends java.lang.Comparable<T>,TBidIter extends IBidIter<T,TBidIter>> boolean IsHeap(TBidIter first,
                                                                                       TBidIter last)

Tests whether the input range is a heap.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

TBidIter - The type of iterators in the specified range.

Parameters:

first - A bidirectional iterator addressing the position of the first element in the range to be tested.

last - A bidirectional iterator addressing the position one past the final element in the range to be tested.

Returns:

True if the input range is a heap; otherwise, false.

IsHeap

public static <T,TBidIter extends IBidIter<T,TBidIter>> boolean IsHeap(TBidIter first,
                                                       TBidIter last,
                                                       IFunc2Arg<T,T,java.lang.Boolean> pred)

Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

TBidIter - The type of iterators in the specified range.

Parameters:

first - A bidirectional iterator addressing the position of the first element in the range to be tested.

last - A bidirectional iterator addressing the position one past the final element in the range to be tested.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

Returns:

True if the input range is a heap; otherwise, false.

IsHeapUntil

public static <T extends java.lang.Comparable<T>,TBidIter extends IBidIter<T,TBidIter>> TBidIter IsHeapUntil(TBidIter first,
                                                                                             TBidIter last)

Tests whether the input range is a heap.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

TBidIter - The type of iterators in the specified range.

Parameters:

first - A bidirectional iterator addressing the position of the first element in the range to be tested.

last - A bidirectional iterator addressing the position one past the final element in the range to be tested.

Returns:

True if the input range is a heap; otherwise, false.

IsHeapUntil

public static <T,TBidIter extends IBidIter<T,TBidIter>> TBidIter IsHeapUntil(TBidIter first,
                                                             TBidIter last,
                                                             IFunc2Arg<T,T,java.lang.Boolean> pred)

Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

TBidIter - The type of iterators in the specified range.

Parameters:

first - A bidirectional iterator addressing the position of the first element in the range to be tested.

last - A bidirectional iterator addressing the position one past the final element in the range to be tested.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

Returns:

True if the input range is a heap; otherwise, false.

IsHeap

public static <T extends java.lang.Comparable<T>> boolean IsHeap(T[] x,
                                                 int first,
                                                 int last)

Tests whether the input range is a heap.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range to be tested.

last - An integer addressing the position one past the final element in the range to be tested.

Returns:

True if the input range is a heap; otherwise, false.

IsHeap

public static <T> boolean IsHeap(T[] x,
                 int first,
                 int last,
                 IFunc2Arg<T,T,java.lang.Boolean> pred)

Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range to be tested.

last - An integer addressing the position one past the final element in the range to be tested.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

Returns:

True if the input range is a heap; otherwise, false.

IsHeapUntil

public static <T extends java.lang.Comparable<T>> int IsHeapUntil(T[] x,
                                                  int first,
                                                  int last)

Tests whether the input range is a heap.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range to be tested.

last - An integer addressing the position one past the final element in the range to be tested.

Returns:

True if the input range is a heap; otherwise, false.

IsHeapUntil

public static <T> int IsHeapUntil(T[] x,
                  int first,
                  int last,
                  IFunc2Arg<T,T,java.lang.Boolean> pred)

Tests whether the input range is a heap where the ordering of elements is specified by a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear with the size of the range.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range to be tested.

last - An integer addressing the position one past the final element in the range to be tested.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

Returns:

True if the input range is a heap; otherwise, false.

MakeHeap

public static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void MakeHeap(TRanIter first,
                                                                                      TRanIter last)

Converts elements from a specified range into a heap in which the first element is the largest.

Remarks: The referenced range must be valid. The complexity is linear, requiring 3 * (last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the range.

last - A random-access iterator addressing the position one past the final element in the range.

MakeHeap

public static <T,TRanIter extends IRanIter<T,TRanIter>> void MakeHeap(TRanIter first,
                                                      TRanIter last,
                                                      IFunc2Arg<T,T,java.lang.Boolean> pred)

Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion is specified with a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear, requiring 3 * (last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the range.

last - A random-access iterator addressing the position one past the final element in the range.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

MakeHeap

public static <T extends java.lang.Comparable<T>> void MakeHeap(T[] x,
                                                int first,
                                                int last)

Converts elements from a specified range into a heap in which the first element is the largest.

Remarks: The referenced range must be valid. The complexity is linear, requiring 3 * (last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range.

last - An integer addressing the position one past the final element in the range.

MakeHeap

public static <T> void MakeHeap(T[] x,
                int first,
                int last,
                IFunc2Arg<T,T,java.lang.Boolean> pred)

Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion is specified with a binary predicate.

Remarks: The referenced range must be valid. The complexity is linear, requiring 3 * (last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the range.

last - An integer addressing the position one past the final element in the range.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

PushHeap

public static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void PushHeap(TRanIter first,
                                                                                      TRanIter last)

Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.

Remarks: The referenced range must be valid and must be a heap (excluding the newly added element at the end). The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

PushHeap

public static <T,TRanIter extends IRanIter<T,TRanIter>> void PushHeap(TRanIter first,
                                                      TRanIter last,
                                                      IFunc2Arg<T,T,java.lang.Boolean> pred)

Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.

Remarks: The referenced range must be valid and must be a heap (excluding the newly added element at the end). The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

PushHeap

public static <T extends java.lang.Comparable<T>> void PushHeap(T[] x,
                                                int first,
                                                int last)

Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.

Remarks: The referenced range must be valid and must be a heap (excluding the newly added element at the end). The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

PushHeap

public static <T> void PushHeap(T[] x,
                int first,
                int last,
                IFunc2Arg<T,T,java.lang.Boolean> pred)

Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.

Remarks: The referenced range must be valid and must be a heap (excluding the newly added element at the end). The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

PopHeap

public static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void PopHeap(TRanIter first,
                                                                                     TRanIter last)

Removes the largest element from the heap and then forms a new heap from the remaining elements.

Remarks: The referenced range must be valid and must be a heap. The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

PopHeap

public static <T,TRanIter extends IRanIter<T,TRanIter>> void PopHeap(TRanIter first,
                                                     TRanIter last,
                                                     IFunc2Arg<T,T,java.lang.Boolean> pred)

Removes the largest element from the heap and then forms a new heap from the remaining elements.

Remarks: The referenced range must be valid and must be a heap. The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

PopHeap

public static <T extends java.lang.Comparable<T>> void PopHeap(T[] x,
                                               int first,
                                               int last)

Removes the largest element from the heap and then forms a new heap from the remaining elements.

Remarks: The referenced range must be valid and must be a heap. The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

PopHeap

public static <T> void PopHeap(T[] x,
               int first,
               int last,
               IFunc2Arg<T,T,java.lang.Boolean> pred)

Removes the largest element from the heap and then forms a new heap from the remaining elements.

Remarks: The referenced range must be valid and must be a heap. The complexity is logarithmic, requiring at most log(last – first) comparisons.

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

SortHeap

public static <T extends java.lang.Comparable<T>,TRanIter extends IRanIter<T,TRanIter>> void SortHeap(TRanIter first,
                                                                                      TRanIter last)

Converts a heap into a sorted range.

Remarks: The referenced range must be valid and must be a heap. After the application of this algorithm, the range it was applied to is no longer a heap. The complexity is at most NlogN, where N = (last – first).

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

SortHeap

public static <T,TRanIter extends IRanIter<T,TRanIter>> void SortHeap(TRanIter first,
                                                      TRanIter last,
                                                      IFunc2Arg<T,T,java.lang.Boolean> pred)

Converts a heap into a sorted range.

Remarks: The referenced range must be valid and must be a heap. After the application of this algorithm, the range it was applied to is no longer a heap. The complexity is at most NlogN, where N = (last – first).

Type Parameters:

T - The type of elements in the specified range.

TRanIter - The type of iterators in the specified range.

Parameters:

first - A random-access iterator addressing the position of the first element in the heap.

last - A random-access iterator addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.

SortHeap

public static <T extends java.lang.Comparable<T>> void SortHeap(T[] x,
                                                int first,
                                                int last)

Converts a heap into a sorted range.

Remarks: The referenced range must be valid and must be a heap. After the application of this algorithm, the range it was applied to is no longer a heap. The complexity is at most NlogN, where N = (last – first).

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

SortHeap

public static <T> void SortHeap(T[] x,
                int first,
                int last,
                IFunc2Arg<T,T,java.lang.Boolean> pred)

Converts a heap into a sorted range.

Remarks: The referenced range must be valid and must be a heap. After the application of this algorithm, the range it was applied to is no longer a heap. The complexity is at most NlogN, where N = (last – first).

Type Parameters:

T - The type of elements in the specified range.

Parameters:

x - The specified array.

first - An integer addressing the position of the first element in the heap.

last - An integer addressing the position one past the final element in the heap.

pred - A user-defined predicate function object that defines the comparison in which one element is less than another.