public class ObjectIndirectHeaps extends Object
An indirect heap is an extension of a semi-indirect heap using also an
inversion array of the same length as the reference array,
satisfying the relation heap[inv[i]]==i
when
inv[i]>=0
, and inv[heap[i]]==i
for all elements in the heap.
Modifier and Type | Method and Description |
---|---|
static <K> int |
downHeap(K[] refArray,
int[] heap,
int[] inv,
int size,
int i,
Comparator<K> c)
Moves the given element down into the indirect heap until it reaches the lowest possible position.
|
static <K> void |
makeHeap(K[] refArray,
int[] heap,
int[] inv,
int size,
Comparator<K> c)
Creates an indirect heap from a given index array.
|
static <K> void |
makeHeap(K[] refArray,
int offset,
int length,
int[] heap,
int[] inv,
Comparator<K> c)
Creates an indirect heap in the given array.
|
static <K> int |
upHeap(K[] refArray,
int[] heap,
int[] inv,
int size,
int i,
Comparator<K> c)
Moves the given element up in the indirect heap until it reaches the highest possible position.
|
public static <K> int downHeap(K[] refArray, int[] heap, int[] inv, int size, int i, Comparator<K> c)
refArray
- the reference array.heap
- the indirect heap (starting at 0).inv
- the inversion array.size
- the number of elements in the heap.i
- the index in the heap of the element to be moved down.c
- a type-specific comparator, or null
for the natural order.i
.public static <K> int upHeap(K[] refArray, int[] heap, int[] inv, int size, int i, Comparator<K> c)
refArray
- the reference array.heap
- the indirect heap (starting at 0).inv
- the inversion array.size
- the number of elements in the heap.i
- the index in the heap of the element to be moved up.c
- a type-specific comparator, or null
for the natural order.i
.public static <K> void makeHeap(K[] refArray, int offset, int length, int[] heap, int[] inv, Comparator<K> 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.inv
- the inversion array.c
- a type-specific comparator, or null
for the natural order.public static <K> void makeHeap(K[] refArray, int[] heap, int[] inv, int size, Comparator<K> c)
refArray
- the reference array.heap
- an array containing indices into refArray
.inv
- the inversion array.size
- the number of elements in the heap.c
- a type-specific comparator, or null
for the natural order.