Package it.unimi.dsi.fastutil.objects
Class ObjectIndirectHeaps
- java.lang.Object
-
- it.unimi.dsi.fastutil.objects.ObjectIndirectHeaps
-
public final class ObjectIndirectHeaps extends java.lang.Object
A class providing static methods and objects that do useful things with indirect heaps.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
wheninv[i]>=0
, andinv[heap[i]]==i
for all elements in the heap.
-
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <K> int
downHeap(K[] refArray, int[] heap, int[] inv, int size, int i, java.util.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, java.util.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, java.util.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, java.util.Comparator<K> c)
Moves the given element up in the indirect heap until it reaches the highest possible position.
-
-
-
Method Detail
-
downHeap
public static <K> int downHeap(K[] refArray, int[] heap, int[] inv, int size, int i, java.util.Comparator<K> c)
Moves the given element down into the indirect heap until it reaches the lowest possible position.- Parameters:
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, ornull
for the natural order.- Returns:
- the new position in the heap of the element of heap index
i
.
-
upHeap
public static <K> int upHeap(K[] refArray, int[] heap, int[] inv, int size, int i, java.util.Comparator<K> c)
Moves the given element up in the indirect heap until it reaches the highest possible position. Note that in principle after this call the heap property may be violated.- Parameters:
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, ornull
for the natural order.- Returns:
- the new position in the heap of the element of heap index
i
.
-
makeHeap
public static <K> void makeHeap(K[] refArray, int offset, int length, int[] heap, int[] inv, java.util.Comparator<K> c)
Creates an indirect heap in the given array.- Parameters:
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, ornull
for the natural order.
-
makeHeap
public static <K> void makeHeap(K[] refArray, int[] heap, int[] inv, int size, java.util.Comparator<K> c)
Creates an indirect heap from a given index array.- Parameters:
refArray
- the reference array.heap
- an array containing indices intorefArray
.inv
- the inversion array.size
- the number of elements in the heap.c
- a type-specific comparator, ornull
for the natural order.
-
-