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

Class DoubleHeap

java.lang.Object

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

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

Direct Known Subclasses:

DoubleMaxHeap, DoubleMinHeap

public abstract class DoubleHeap
extends AbstractHeap

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
protected double[]	queue Heap storage: queue

Fields inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.AbstractHeap

DEFAULT_INITIAL_CAPACITY, modCount, size, validSize

Constructor Summary

Constructors

Constructor and Description
DoubleHeap(int size) Constructor with initial capacity.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(double key) Add a key-value pair to the heap
void	add(double key, int max) Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)
void	clear() Delete all elements from the heap.
protected abstract boolean	comp(double o1, double o2) Compare two objects
protected void	ensureValid() Repair the heap
protected boolean	heapifyDown(int ipos, double curkey) Execute a "Heapify Downwards" aka "SiftDown".
protected void	heapifyUp(int pos, double curkey) Execute a "Heapify Upwards" aka "SiftUp".
double	peek() Get the current top key
double	poll() Remove the first element
protected double	removeAt(int pos) Remove the element at the given position.
double	replaceTopElement(double e) Combined operation that removes the top element, and inserts a new element instead.
protected void	resize(int requiredSize) Test whether we need to resize to have the requested capacity.

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.datastructures.heap.AbstractHeap

desiredSize, heapModified, size

Methods inherited from class java.lang.Object

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

Field Detail

queue

protected transient double[] queue

Heap storage: queue

Constructor Detail

DoubleHeap

public DoubleHeap(int size)

Constructor with initial capacity.

Parameters:

size - initial capacity

Method Detail

add

public void add(double key)

Add a key-value pair to the heap

Parameters:

key - Key

add

public void add(double key,
       int max)

Add a key-value pair to the heap, except if the new element is larger than the top, and we are at design size (overflow)

Parameters:

key - Key

max - Maximum size of heap

replaceTopElement

public double replaceTopElement(double e)

Combined operation that removes the top element, and inserts a new element instead.

Parameters:

e - New element to insert

Returns:

Previous top element of the heap

peek

public double peek()

Get the current top key

Returns:

Top key

poll

public double poll()

Remove the first element

Returns:

Top element

ensureValid

protected void ensureValid()

Repair the heap

removeAt

protected double removeAt(int pos)

Remove the element at the given position.

Parameters:

pos - Element position.

Returns:

Removed element

heapifyUp

protected void heapifyUp(int pos,
             double curkey)

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

Parameters:

pos - insertion position

curkey - Current key

heapifyDown

protected boolean heapifyDown(int ipos,
                  double curkey)

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

Parameters:

ipos - re-insertion position

curkey - Current key

Returns:

true when the order was changed

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.

Overrides:

clear in class AbstractHeap

comp

protected abstract boolean comp(double o1,
           double o2)

Compare two objects