All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class COM.objectspace.jgl.algorithms.Heap

java.lang.Object
   |
   +----COM.objectspace.jgl.algorithms.Heap

public final class Heap
extends Object
The Heap class contains generic heap algorithms.

See Also:
HeapExamples

Method Index

 o makeHeap(BidirectionalIterator, BidirectionalIterator)
Arrange a sequence into a heap that is ordered according to the object's hash codes.
 o makeHeap(BidirectionalIterator, BidirectionalIterator, BinaryPredicate)
Arrange a sequence into a heap that is ordered according to a comparator.
 o popHeap(BidirectionalIterator, BidirectionalIterator)
Assuming that a sequence is organized as a heap, swap its first and last elements and then reorganize every element except for the last element to be a heap.
 o popHeap(BidirectionalIterator, BidirectionalIterator, BinaryPredicate)
Assuming that a sequence is organized as a heap, swap its first and last elements and then reorganize every element except for the last element to be a heap.
 o pushHeap(BidirectionalIterator, BidirectionalIterator)
Assuming that a sequence is already organized as a heap, insert the element that is immediately after the sequence into the heap.
 o pushHeap(BidirectionalIterator, BidirectionalIterator, BinaryPredicate)
Assuming that a sequence is already organized as a heap, insert the element that is immediately after the sequence into the heap.
 o sortHeap(BidirectionalIterator, BidirectionalIterator)
Sort a heap according to the object's hash codes.
 o sortHeap(BidirectionalIterator, BidirectionalIterator, BinaryPredicate)
Sort a heap according to a comparator.

Methods

 o pushHeap
 public static void pushHeap(BidirectionalIterator first,
                             BidirectionalIterator last)
Assuming that a sequence is already organized as a heap, insert the element that is immediately after the sequence into the heap. The elements are organized according to their hash code. The time complexity is O(log N), where N is the size of the heap. Space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o pushHeap
 public static void pushHeap(BidirectionalIterator first,
                             BidirectionalIterator last,
                             BinaryPredicate comparator)
Assuming that a sequence is already organized as a heap, insert the element that is immediately after the sequence into the heap. The elements are organized according to a specified comparator. The time complexity is O(log N), where N is the size of the heap. Space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
comparator - A binary predicate that returns true if its first operand is "less" than its second operand.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o popHeap
 public static void popHeap(BidirectionalIterator first,
                            BidirectionalIterator last)
Assuming that a sequence is organized as a heap, swap its first and last elements and then reorganize every element except for the last element to be a heap. The elements are organized according to their hash code. Time complexity is 2*log(last-first) and space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o popHeap
 public static void popHeap(BidirectionalIterator first,
                            BidirectionalIterator last,
                            BinaryPredicate comparator)
Assuming that a sequence is organized as a heap, swap its first and last elements and then reorganize every element except for the last element to be a heap. The elements are organized according to a specified comparator. Time complexity is 2*log(last-first) and space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
comparator - A binary predicate that returns true if its first operand is "less" than its second operand.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o makeHeap
 public static void makeHeap(BidirectionalIterator first,
                             BidirectionalIterator last)
Arrange a sequence into a heap that is ordered according to the object's hash codes. The time complexity is linear and the space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o makeHeap
 public static void makeHeap(BidirectionalIterator first,
                             BidirectionalIterator last,
                             BinaryPredicate comparator)
Arrange a sequence into a heap that is ordered according to a comparator. The time complexity is linear and the space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
comparator - A binary predicate that returns true if its first operand is "less" than its second operand.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o sortHeap
 public static void sortHeap(BidirectionalIterator first,
                             BidirectionalIterator last)
Sort a heap according to the object's hash codes. Time complexity is N*log(N) and the space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the heap.
last - An iterator positioned immediately after the last element of the heap.
Throws: IllegalArgumentException
If the iterators are incompatible.
 o sortHeap
 public static void sortHeap(BidirectionalIterator first,
                             BidirectionalIterator last,
                             BinaryPredicate comparator)
Sort a heap according to a comparator. Time complexity is N*log(N) and the space complexity is constant.

Parameters:
first - An iterator positioned at the first element of the sequence.
last - An iterator positioned immediately after the last element of the sequence.
comparator - A binary predicate that returns true if its first operand is "less" than its second operand.
Throws: IllegalArgumentException
If the iterators are incompatible.

All Packages  Class Hierarchy  This Package  Previous  Next  Index