Package it.unimi.dsi.fastutil.ints
Class IntIndirectHeaps
java.lang.Object
it.unimi.dsi.fastutil.ints.IntIndirectHeaps
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
when
inv[i]>=0
, and inv[heap[i]]==i
for all elements in the heap.
-
Method Summary
Modifier and TypeMethodDescriptionstatic int
downHeap
(int[] refArray, int[] heap, int[] inv, int size, int i, IntComparator c) Moves the given element down into the indirect heap until it reaches the lowest possible position.static void
makeHeap
(int[] refArray, int[] heap, int[] inv, int size, IntComparator c) Creates an indirect heap from a given index array.static void
makeHeap
(int[] refArray, int offset, int length, int[] heap, int[] inv, IntComparator c) Creates an indirect heap in the given array.static int
upHeap
(int[] refArray, int[] heap, int[] inv, int size, int i, IntComparator c) Moves the given element up in the indirect heap until it reaches the highest possible position.
-
Method Details
-
downHeap
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
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 void makeHeap(int[] refArray, int offset, int length, int[] heap, int[] inv, IntComparator 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
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.
-