it.unimi.dsi.fastutil.longs
Class LongSemiIndirectHeaps

java.lang.Object
  it.unimi.dsi.fastutil.longs.LongSemiIndirectHeaps

public class LongSemiIndirectHeaps

extends Object

A class providing static methods and objects that do useful things with semi-indirect heaps.

A semi-indirect heap is based on a reference array. Elements of a semi-indirect 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).

Method Summary

static int	downHeap(long[] refArray, int[] heap, int size, int i, LongComparator c) Moves the given element down into the semi-indirect heap until it reaches the lowest possible position.
static void	makeHeap(long[] refArray, int[] heap, int size, LongComparator c) Creates a semi-indirect heap from a given index array.
static void	makeHeap(long[] refArray, int offset, int length, int[] heap, LongComparator c) Creates a semi-indirect heap in the given array.
static int[]	makeHeap(long[] refArray, int offset, int length, LongComparator c) Creates a semi-indirect heap, allocating its heap array.
static int	upHeap(long[] refArray, int[] heap, int size, int i, LongComparator c) Moves the given element up in the semi-indirect heap until it reaches the highest possible position.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

downHeap

public static int downHeap(long[] refArray,
                           int[] heap,
                           int size,
                           int i,
                           LongComparator c)

Moves the given element down into the semi-indirect heap until it reaches the lowest possible position.

Parameters:

refArray - the reference array.

heap - the semi-indirect 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 type-specific comparator, or null for the natural order.

Returns:

the new position in the heap of the element of heap index i.

upHeap

public static int upHeap(long[] refArray,
                         int[] heap,
                         int size,
                         int i,
                         LongComparator c)

Moves the given element up in the semi-indirect heap until it reaches the highest possible position.

Parameters:

refArray - the reference array.

heap - the semi-indirect 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 type-specific comparator, or null for the natural order.

Returns:

the new position in the heap of the element of heap index i.

makeHeap

public static void makeHeap(long[] refArray,
                            int offset,
                            int length,
                            int[] heap,
                            LongComparator c)

Creates a semi-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.

c - a type-specific comparator, or null for the natural order.

makeHeap

public static int[] makeHeap(long[] refArray,
                             int offset,
                             int length,
                             LongComparator c)

Creates a semi-indirect heap, allocating its heap 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.

c - a type-specific comparator, or null for the natural order.

Returns:

the heap array.

makeHeap

public static void makeHeap(long[] refArray,
                            int[] heap,
                            int size,
                            LongComparator c)

Creates a semi-indirect heap from a given index array.

Parameters:

refArray - the reference array.

heap - an array containing indices into refArray.

size - the number of elements in the heap.

c - a type-specific comparator, or null for the natural order.