public final class IntSemiIndirectHeaps extends Object
A semiindirect heap is based on a reference array. Elements of a semiindirect heap are integers that index the reference array (note that in an indirect heap you can also map elements of the reference array to heap positions).
Modifier and Type  Method and Description 

static int 
downHeap(int[] refArray,
int[] heap,
int size,
int i,
IntComparator c)
Moves the given element down into the semiindirect heap until it reaches
the lowest possible position.

static int 
front(int[] refArray,
int[] heap,
int size,
int[] a)
Retrieves the front of a heap in a given array.

static int 
front(int[] refArray,
int[] heap,
int size,
int[] a,
IntComparator c)
Retrieves the front of a heap in a given array using a given comparator.

static void 
makeHeap(int[] refArray,
int[] heap,
int size,
IntComparator c)
Creates a semiindirect heap from a given index array.

static void 
makeHeap(int[] refArray,
int offset,
int length,
int[] heap,
IntComparator c)
Creates a semiindirect heap in the given array.

static int[] 
makeHeap(int[] refArray,
int offset,
int length,
IntComparator c)
Creates a semiindirect heap, allocating its heap array.

static int 
upHeap(int[] refArray,
int[] heap,
int size,
int i,
IntComparator c)
Moves the given element up in the semiindirect heap until it reaches the
highest possible position.

public static int downHeap(int[] refArray, int[] heap, int size, int i, IntComparator c)
refArray
 the reference array.heap
 the semiindirect heap (starting at 0).size
 the number of elements in the heap.i
 the index in the heap of the element to be moved down.c
 a typespecific comparator, or null
for the natural
order.i
.public static int upHeap(int[] refArray, int[] heap, int size, int i, IntComparator c)
refArray
 the reference array.heap
 the semiindirect heap (starting at 0).size
 the number of elements in the heap.i
 the index in the heap of the element to be moved up.c
 a typespecific comparator, or null
for the natural
order.i
.public static void makeHeap(int[] refArray, int offset, int length, int[] heap, IntComparator c)
refArray
 the reference array.offset
 the first element of the reference array to be put in the
heap.length
 the number of elements to be put in the heap.heap
 the array where the heap is to be created.c
 a typespecific comparator, or null
for the natural
order.public static int[] makeHeap(int[] refArray, int offset, int length, IntComparator c)
refArray
 the reference array.offset
 the first element of the reference array to be put in the
heap.length
 the number of elements to be put in the heap.c
 a typespecific comparator, or null
for the natural
order.public static void makeHeap(int[] refArray, int[] heap, int size, IntComparator c)
refArray
 the reference array.heap
 an array containing indices into refArray
.size
 the number of elements in the heap.c
 a typespecific comparator, or null
for the natural
order.public static int front(int[] refArray, int[] heap, int size, int[] a)
The front of a semiindirect heap is the set of indices whose associated elements in the reference array are equal to the element associated to the first index.
In several circumstances you need to know the front, and scanning linearly the entire heap is not the best strategy. This method simulates (using a partial linear scan) a breadthfirst visit that terminates when all visited nodes are larger than the element associated to the top index, which implies that no elements of the front can be found later. In most cases this trick yields a significant improvement.
refArray
 the reference array.heap
 an array containing indices into refArray
.size
 the number of elements in the heap.a
 an array large enough to hold the front (e.g., at least long
as refArray
).a
).public static int front(int[] refArray, int[] heap, int size, int[] a, IntComparator c)
The front of a semiindirect heap is the set of indices whose associated elements in the reference array are equal to the element associated to the first index.
In several circumstances you need to know the front, and scanning linearly the entire heap is not the best strategy. This method simulates (using a partial linear scan) a breadthfirst visit that terminates when all visited nodes are larger than the element associated to the top index, which implies that no elements of the front can be found later. In most cases this trick yields a significant improvement.
refArray
 the reference array.heap
 an array containing indices into refArray
.size
 the number of elements in the heap.a
 an array large enough to hold the front (e.g., at least long
as refArray
).c
 a typespecific comparator.a
).