de.lmu.ifi.dbs.elki.utilities.datastructures.heap

Class DoubleObjMaxHeap<V>

java.lang.Object

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.DoubleObjMaxHeap<V>

Type Parameters:

V - value type

public class DoubleObjMaxHeap<V>
extends Object

Basic in-memory heap structure. This heap is built lazily: if you first add many elements, then poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in O(n log n). This is implemented via a simple validTo counter.

Field Summary

Fields

Modifier and Type	Field and Description
private static int	DEFAULT_INITIAL_CAPACITY Default initial capacity
protected double[]	keys Heap storage: keys
int	modCount (Structural) modification counter.
protected int	size Current number of objects
protected int	validSize Indicate up to where the heap is valid
protected Object[]	values Heap storage: values

Constructor Summary

Constructors

Constructor and Description
DoubleObjMaxHeap() Default constructor: default capacity, natural ordering.
DoubleObjMaxHeap(int size) Constructor with initial capacity and Comparator.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(double key, V val) Add a key-value pair to the heap
protected String	checkHeap() Test whether the heap is still valid.
void	clear() Delete all elements from the heap.
protected void	ensureValid() Repair the heap
protected boolean	heapifyDown(int ipos, double curkey, Object curval) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUp(int pos, double curkey, Object curval) Execute a "Heapify Upwards" aka "SiftUp".
double	peekKey() Get the current top key
V	peekValue() Get the current top value
void	poll() Remove the first element
protected void	removeAt(int pos) Remove the element at the given position.
protected void	resize(int requiredSize) Test whether we need to resize to have the requested capacity.
int	size() Query the size

Methods inherited from class java.lang.Object

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

Field Detail

keys

protected double[] keys

Heap storage: keys

values

protected Object[] values

Heap storage: values

size

protected int size

Current number of objects

validSize

protected int validSize

Indicate up to where the heap is valid

modCount

public transient int modCount

(Structural) modification counter. Used to invalidate iterators.

DEFAULT_INITIAL_CAPACITY

private static final int DEFAULT_INITIAL_CAPACITY

Default initial capacity

See Also:

Constant Field Values

Constructor Detail

DoubleObjMaxHeap

public DoubleObjMaxHeap()

Default constructor: default capacity, natural ordering.

DoubleObjMaxHeap

public DoubleObjMaxHeap(int size)

Constructor with initial capacity and Comparator.

Parameters:

size - initial capacity

Method Detail

add

public boolean add(double key,
          V val)

Add a key-value pair to the heap

Parameters:

key - Key

val - Value

Returns:

Success code

peekKey

public double peekKey()

Get the current top key

Returns:

Top key

peekValue

public V peekValue()

Get the current top value

Returns:

Value

poll

public void poll()

Remove the first element

ensureValid

protected void ensureValid()

Repair the heap

removeAt

protected void removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element position.

heapifyUp

protected void heapifyUp(int pos,
             double curkey,
             Object curval)

Execute a "Heapify Upwards" aka "SiftUp". Used in insertions.

Parameters:

pos - insertion position

curkey - Current key

curval - Current value

heapifyDown

protected boolean heapifyDown(int ipos,
                  double curkey,
                  Object curval)

Execute a "Heapify Downwards" aka "SiftDown". Used in deletions.

Parameters:

ipos - re-insertion position

curkey - Current key

curval - Current value

Returns:

true when the order was changed

size

public int size()

Query the size

Returns:

Size

resize

protected final void resize(int requiredSize)

Test whether we need to resize to have the requested capacity.

Parameters:

requiredSize - required capacity

clear

public void clear()

Delete all elements from the heap.

checkHeap

protected String checkHeap()

Test whether the heap is still valid. Debug method.

Returns:

null when the heap is correct