it.unimi.dsi.fastutil.objects

Class ObjectHeaps

java.lang.Object

it.unimi.dsi.fastutil.objects.ObjectHeaps

public class ObjectHeaps
extends Object

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

The static methods of this class allow to treat arrays as 0-based heaps. They are used in the implementation of heap-based queues, but they may be also used directly.

Method Summary

Methods

Modifier and Type	Method and Description
static <K> int	downHeap(K[] heap, int size, int i, Comparator<? super K> c) Moves the given element down into the heap until it reaches the lowest possible position.
static <K> void	makeHeap(K[] heap, int size, Comparator<K> c) Makes an array into a heap.
static <K> int	upHeap(K[] heap, int size, int i, Comparator<K> c) Moves the given element up in the heap until it reaches the highest possible position.

Methods inherited from class java.lang.Object

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

Method Detail

downHeap

public static <K> int downHeap(K[] heap,
               int size,
               int i,
               Comparator<? super K> c)

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

Parameters:

heap - the heap (starting at 0).

size - the number of elements in the heap.

i - the index of the element that must be moved down.

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

Returns:

the new position of the element of index i.

upHeap

public static <K> int upHeap(K[] heap,
             int size,
             int i,
             Comparator<K> c)

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

Parameters:

heap - the heap (starting at 0).

size - the number of elements in the heap.

i - the index of the element that must be moved up.

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

Returns:

the new position of the element of index i.

makeHeap

public static <K> void makeHeap(K[] heap,
                int size,
                Comparator<K> c)

Makes an array into a heap.

Parameters:

heap - the heap (starting at 0).

size - the number of elements in the heap.

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